백준 1149

문제

---

DP

DP의 각 요소는 해당 색을 해당 번호의 집에 칠하였을 때의 최소 비용을 저장

1번부터 순서대로 집을 색칠한다고 가정

1) 먼저 1번 집을 칠할 비용은 각각의 비용 그대로 저장

집	RED	GREEN	BLUE
1번	cost[0][0]	cost[0][1]	cost[0][2]
2번
...
N번

2) 이제 2번 집을 색칠하는데

2번 집을 RED로 칠할 경우 --> 1번 집은 GREEN or BLUE 여야 함
따라서 최소비용은
dp[1][0] == Math.min(cost[0][1], cost[0][2]) + cost[1][0]

3) 2)의 원리를 확장시키면

N번 집을 RED로 칠할 경우 --> N - 1번 집은 GREEN or BLUE

따라서 최소 비용(dp[N-1][0])은

N번 집을 RED로 칠할 비용(cost[N-1][0])과

(N-1번 째 집은 GREEN or BLUE && N-1개의 집을 칠할 때)의 최소 비용

예시를 위해 마지막 집의 색이 RED일 때만을 고려했지만

최종적으로 최소비용은

마지막 집이 RED, GREEN, BLUE 일 때의 최소 비용을 모두 구해본 뒤

그 중의 최소값을 구하면 정답

---

Code

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P1149 {

	final private static int RED = 0;
	final private static int GREEN = 1;
	final private static int BLUE = 2;

	private static int[][] cost;
	private static int[][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());
		cost = new int[N][3];
		dp = new int[N][3];

		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());

			cost[i][RED] = Integer.parseInt(st.nextToken());
			cost[i][GREEN] = Integer.parseInt(st.nextToken());
			cost[i][BLUE] = Integer.parseInt(st.nextToken());
		}

		dp[0][RED] = cost[0][RED];
		dp[0][GREEN] = cost[0][GREEN];
		dp[0][BLUE] = cost[0][BLUE];
		
		System.out.println(
				Math.min(total_minCost(N - 1, RED), 
						Math.min(total_minCost(N - 1, GREEN), 
								total_minCost(N - 1, BLUE))
						)
				);
	}

	private static int total_minCost(int N, int color) {

		if(dp[N][color] == 0) {
			switch(color) {
				case RED: 
					dp[N][RED] = Math.min(total_minCost(N - 1, GREEN), total_minCost(N - 1, BLUE)) + cost[N][RED];
					break;
				case GREEN:
					dp[N][GREEN] = Math.min(total_minCost(N - 1, RED), total_minCost(N - 1, BLUE)) + cost[N][GREEN];
					break;
				case BLUE:
					dp[N][BLUE] = Math.min(total_minCost(N - 1, RED), total_minCost(N - 1, GREEN)) + cost[N][BLUE];
					break;
			}
		}
		return dp[N][color];
	}

}

---

참고 : https://st-lab.tistory.com/128