문제 설명

N개의 집이 선분 위에 순서대로 존재한다. 이 집들을 각각 빨,초,파 중 하나로 칠할건데, 이웃한 집끼리는 같은 색일 수 없다. 즉, 연속된 두 개 이상의 색상이 나올 수 없다는 말이다.
그리고 각 집마다 자신을 빨,초,파로 칠했을때의 비용이 주어진다.
이때, 모든 집을 칠했을때의 최소 비용을 구하기.

접근

시간제한은 0.5초이다.
일단 무식하게 브루트포스로 모든 경우를 본다면, i집에서 빨강을 칠한다면, 그 다음집의 선택권은 2가지다. 그리고 그 다음집도 2가지다. 이렇게 생각해보면, 1번째집을 빨강으로 칠했을때의 모든 경우 가지수는 2의 999승이다. 그리고 1번째 집을 파랑, 초록으로 칠한것까지 고려한다면 여기서 세 배가 된다.
일단 가짓수가 너무 많다. 이런 경우는 보통 DP로 먼저 생각해본다. DP는 뒤에서부터 시작해서 역추적하는 방식으로 생각해봐야 점화식을 구하기 쉬우므로 이번에는 N번째 집 먼저 칠한다고 생각해보자. 또한, DP로 풀때는 역추적하다가 중복된 연산이 나오는지를 잘 봐야한다.

N번째 집을 빨강으로 칠한다면, 그 이전 집은 초록 아니면 파랑이여야 한다.
N-1번째집이 초록인 경우를 생각해보자. 그러면, 그 이전집인 N-2번집은 빨강 아니면 파랑이다.
이번에는 N-1번째 집이 파랑이 경우를 생각해보자. 그러면 N-2번 집은 빨강 아니면 초록이다.

엇, 중복이 나왔다. N-2번째 집이 빨강인 경우가 중복의 연산이다.
그렇다면, 이 중복 연산을 다음번에 또 안할 수 있도록 정보를 기억해야한다.
즉, 1번집부터 i번째집까지 색상을 모두 칠했는데 i번째집이 빨강인 경우, 파랑인 경우, 초록인 경우일때의 색칠 최소 비용을 어딘가에 저장해놓으면 된다.

점화식

dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + (i번째 집을 0번색으로 칠하는데 비용)

풀이

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

public class Main {
    static int[][] dp;
    static int[][] house_cost;
    static int N;

    static int dfs(int houseNumber, int curColor) {
    	// 이미 구한거면 다시 계산하지 말라고, 걸어놓은 장치임
        if (dp[houseNumber][curColor] != 0) return dp[houseNumber][curColor];
        if (curColor == 0) {
            dp[houseNumber][curColor] = Math.min(dfs(houseNumber - 1, 1), dfs(houseNumber - 1, 2)) + house_cost[houseNumber][curColor];
        } else if (curColor == 1) {
            dp[houseNumber][curColor] = Math.min(dfs(houseNumber - 1, 0), dfs(houseNumber - 1, 2)) + house_cost[houseNumber][curColor];
        } else {
            dp[houseNumber][curColor] = Math.min(dfs(houseNumber - 1, 0), dfs(houseNumber - 1, 1)) + house_cost[houseNumber][curColor];
        }
        return dp[houseNumber][curColor];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new int[N][3];
        house_cost = new int[N][3];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            house_cost[i][0] = Integer.parseInt(st.nextToken());
            house_cost[i][1] = Integer.parseInt(st.nextToken());
            house_cost[i][2] = Integer.parseInt(st.nextToken());
        }

        dp[0][0] = house_cost[0][0];
        dp[0][1] = house_cost[0][1];
        dp[0][2] = house_cost[0][2];

        int[] results = {dfs(N - 1, 0), dfs(N - 1, 1), dfs(N - 1, 2)};
        System.out.println(Arrays.stream(results).min().getAsInt());
    }
}

여기서 Arrays.stream(배열).min().getAsInt() 라는 함수를 새로 배웠다.