문제 접근

아주 전형적인 쉬운 dp 유형이다.
문제에서 원하는 조건대로 경우의 수를 트리 구조로 만들어 나가다 보면, 중복 연산 지점이 발생한다.

보통 쉬운 dp들은 뒤에서부터 dfs를 시작해서 한 칸씩 앞으로 재귀적으로 댕겨나가면서 구해나가는 방식이다. 물론 역으로 해도 되지만 개인적으로는 이 방식이 떠올리기 쉬운 것 같다.

이 문제도 동일하게, 맨 뒤의 집부터 빨강으로 칠하는 경우의 수, 파랑으로 칠하는 경우의 수, 초록으로 칠하는 경우의 수, 각각에 대해 트리 구조를 그려보자.
그러면, 특정 K번째 집을 C색상으로 칠하는 경우에 대해 중복으로 필요한 경우가 많이 생길 것이다.
이를 위해, dp[K][C] 를 저장해놓으면 된다.
참고로 점화식은 dp[k+1][C1] = Math.min(dp[k][C2], dp[k][C3]) + houses[k+1][C1] 이다.

문제 풀이

import java.io.*;
import java.util.*;

class Main {
    static int N;
    static int[][] dp;
    static int[][] houses;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        houses = new int[N][3];
        dp = new int[N][3];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            houses[i][0] = Integer.parseInt(st.nextToken());
            houses[i][1] = Integer.parseInt(st.nextToken());
            houses[i][2] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < 3; i++) dp[0][i] = houses[0][i];
        int result = 20_0000_0000;
        for (int i = 0; i < 3; i++) {
            result = Math.min(result, dfs(N - 1, i));
        }
        System.out.print(result);
    }

    static int dfs(int curN, int color) {
        if (dp[curN][color] != 0) return dp[curN][color];
        int sum = houses[curN][color];
        if (color == 0) {
            sum += Math.min(dfs(curN - 1, 1), dfs(curN-1, 2));
        } else if (color == 1) {
            sum += Math.min(dfs(curN - 1, 0), dfs(curN-1, 2));
        } else {
            sum += Math.min(dfs(curN - 1, 0), dfs(curN-1, 1));
        }

        dp[curN][color] = sum;
        return sum;
    }
}