문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

풀이

해당 문제는 처음에 이해하기 어려웠다. 각 집마다 R,G,B의 색을 칠하는 비용이 주어지고 모든 집을 색칠하는데 드는 최소 비용을 구하는 것이다.

하지만 쉽게 생각해서 인접한 집의 색이 다르면서 최소인것만 고르면 틀리게 나온다. 따라서 모든 경우를 고려하여 비용을 구한 뒤 제일 작은 것을 출력하면 된다.

문제 예시로 예를들어보자. 각 집을 칠하는 비용을 cost[N][3]라 하자. (cost[N][0] : RED, cost[N][1] : GREEN, cost[N][2] : BLUE)

1번 집 : cost[1][0] , cost[1][1], cost[1][2]
2번 집 :
cost[2][0] + min(cost[1][1], cost[1][2]) ,
cost[2][1] + min(cost[1][0], cost[1][2]) ,
cost[2][2] + min(cost[1][0], cost[1][1])
3번 집 :
cost[3][0] + min(cost[2][1], cost[2][2]) ,
cost[3][1] + min(cost[2][0], cost[2][2]) ,
cost[3][2] + min(cost[2][0], cost[2][1])
...
N번 집 :
cost[N][0] + min(cost[N-1][1], cost[N-1][2]) ,
cost[N][1] + min(cost[N-1][0], cost[N-1][2]) ,
cost[N][2] + min(cost[N-1][0], cost[N-1][1])

이렇게 각 집마다 R,G,B 로 색칠했을 때의 비용이 누적되서 나오게 된다.
그러면 문제에서 요구하는 최소 비용을 구하기 위해서는 min(cost[N][0], cost[N][1], cost[N][2])을 구하면 되는 것이다.

소스

import java.util.*;

public class Main {
	public static int n;
	public static int[][] cost = new int[1001][3];
	public static int[][] d = new int[1001][3];

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

		n = sc.nextInt();

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

		for (int i = 1; i <= n; i++) {
			// RED
			d[i][0] = Math.min(d[i - 1][1], d[i - 1][2]) + cost[i][0];
			// GREEN
			d[i][1] = Math.min(d[i - 1][0], d[i - 1][2]) + cost[i][1];
			// BLUE
			d[i][2] = Math.min(d[i - 1][0], d[i - 1][1]) + cost[i][2];
		}

		int ans = Math.min(d[n][0], Math.min(d[n][1], d[n][2]));
		System.out.println(ans);
	}

}