[백준] 1149. RGB거리

문제 링크

[백준] 1149. RGB거리

풀이 과정

각 집은 이웃한 집들과의 색깔이 달라야 합니다.

위처럼 2번 집을 R로 칠하게 되면, 아래 그림과 같이 이웃한 양쪽 집들은 R가 아닌 G 또는 B로 칠해져야 합니다.

Bottom-up 방식으로 가장 왼쪽 집부터 시작해, 각 색상을 고를때 집을 칠하는 누적 비용이 최소 가 되도록 선택하고 그 값을 저장합니다. 다음번 색상을 고를 땐, 해당 색상을 제외한 색상을 선택했을 때의 최소 비용에 현재 고른 색상으로 칠하는 비용을 더합니다.

아래 문제의 입력 예를 통해 코드로 어떻게 작동되는 지 알아보겠습니다.

3
26 40 83
49 60 57
13 89 99

memoization 을 위한 d 배열을 생성하고, 0번 인덱스의 요소들을 cost[0] 배열의 값들로 초기화합니다. 이는 첫 번째 집까지에 대한 최소 색칠 비용은 이전 단계가 없기 때문에, 해당 색으로 칠한 비용만이 소모되기 때문입니다.

다음 1번째 집을 칠하는 방법의 가짓수는 다음과 같습니다.

d[1][0] 값은 이전 0번째 인덱스의 집에서 G 또는 B로 칠한 후 현재 집을 R로 칠하는 비용이 들어갑니다. 이전 0번째 집을 G로 칠했을 때의 누적 비용은 40, B로 칠했을 때의 누적 비용은 83이며, 더 적은 비용의 40을 선택한 후에 현재 집을 R로 칠하는 비용 cost[1][0] 을 더해 저장하게 됩니다. 이와 같이 진행하면, 각 단계에서 집을 각각 R, G, B로 칠했을 때의 최소의 누적 비용을 구할 수 있게 됩니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[][] cost = new int[N][3];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                cost[i][j] = sc.nextInt();
            }
        }

        int[][] d = new int[N][3];
        d[0] = cost[0].clone();

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = 0; k < 3; k++) {
                    if (j == k) continue;
                    min = Math.min(min, d[i - 1][k]);
                }
                d[i][j] = min + cost[i][j];
            }
        }

        int answer = Integer.MAX_VALUE;
        for (int j = 0; j < 3; j++)
            answer = Math.min(answer, d[N - 1][j]);

        System.out.println(answer);
    }
}