1149번 RGB거리 / BOJ / acmicpc.net

문제링크 : https://www.acmicpc.net/problem/1149
제출링크 : https://www.acmicpc.net/source/17183603

i 가 집의 순서, j 가 색깔(RGB)라고 정의하면,
문제에서, 모든 이웃은 같은 색으로 칠할 수 없다. 그리고 i의 이웃은 i-1 과 i+1 이다. 라고 했는대요.
이부분에서 i-1과 i+1을 동시에 고려해야 하는 것으로, 오해를 할 수 있습니다.
주의 깊게 봐야할 부분이 모든 이웃 입니다. 즉, i-1 과 i 번째 집의 색이 다르기만 하면, 조건을 만족 시킬 수 있습니다.
따라서, i+1은 고려하지 않아도, 위의 조건을 만족시킬 수 있습니다.

점화식(Recurrence Relation)은 아래와 같이 만들 수 있습니다. 앞집(i-1)과 색이 달라야 하기 때문에

\begin{aligned}
1 \leq i \leq N \\
1 \leq j \leq 3 \\
dp_{i,1} = dp_{i,1} + min(dp_{i-1,2}, dp_{i-1,3}) \\
dp_{i,2} = dp_{i,2} + min(dp_{i-1,1}, dp_{i-1,3}) \\
dp_{i,3} = dp_{i,3} + min(dp_{i-1,1}, dp_{i-1,2}) \\
\end{aligned}

import java.util.Scanner;

public class Main {
    public void solve() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] c = new int[N][3];

        for(int i=0; i<N; ++i) {
            c[i][0] = sc.nextInt();
            c[i][1] = sc.nextInt();
            c[i][2] = sc.nextInt();
        }

        for(int i=1; i<N; ++i) {
            c[i][0] += Math.min(c[i-1][1], c[i-1][2]);
            c[i][1] += Math.min(c[i-1][0], c[i-1][2]);
            c[i][2] += Math.min(c[i-1][0], c[i-1][1]);
        }

        int r = Math.min(c[N-1][0], c[N-1][1]);
        r = Math.min(c[N-1][2], r);

        System.out.println(r);
    }

    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
}