문제 이해

집이 N개가 있다.
이 때 집은 빨강 초록 파랑 하나의 색으로만 칠할 수 있는데, 이웃하는 집의 색깔은 달라야 한다.

이런 제한 조건을 만족시키면서 모든 집을 칠하려고 할 때 드는 비용의 최솟값을 구하는 문제이다.

---

문제 풀이

먼저, 이 문제를 풀 때 하나하나 집을 칠해보는 경우의 수 이외에는 방법이 생각나지 않았다.
그렇다면, 이런 Brute-Force를 어떻게 효율적으로 활용할지가 중요할 것이다.

현재 내가 빨간색 집을 칠했다고 가정하자.
그렇다면 이전 집에는 파란색, 혹은 초록색 집이 칠해져 있을 것이다.
즉, 내가 T번째 집을 칠할 때 (T-1)번째 집이 어느 색으로, 얼마만큼의 비용으로 칠해져있는지 알고 있다면 문제를 풀기 쉬울 것이라고 생각했다.

따라서 배열을 N*3배열로 만들었다.
DP[T][0] : T번째 집을 빨간색으로 칠했을 경우 최소 비용
DP[T][1] : T번째 집을 파란색으로 칠했을 경우 최소 비용
DP[T][2] : T번째 집을 초록색으로 칠했을 경우 최소 비용

N번째 집에 특정 색깔을 칠해야 한다는 조건이 없으므로, 답은 DP[N][0], DP[N][1], DP[N][2] 중 최솟값이 될 것이다.
또한, 연속된 집은 같은 색깔로 칠할 수 없으므로 아래와 같은 점화식을 가질 것이다.

DP[T][0] = min(DP[T-1][1], DP[T-1][2]) + 빨간색 집으로 칠하는 비용
DP[T][1] = min(DP[T-1][0], DP[T-1][2]) + 파란색 집으로 칠하는 비용
DP[T][2] = min(DP[T-1][0], DP[T-1][1]) + 초록색 집으로 칠하는 비용

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[][] cost;
    // 처음 cost에 값이 저장될 때는 
    // cost[T][0] : T번째 집을 빨간색으로 칠하는 비용
    // cost[T][1] : T번째 집을 파란색으로 칠하는 비용
    // cost[T][2] : T번째 집을 초록색으로 칠하는 비용
    // 이 저장될 것이다.
	
	static void dp() {
		for(int i =1;i<N+1;i++) {
			cost[i][0] = Math.min(cost[i-1][1], cost[i-1][2]) 
                                                            + cost[i][0];
			cost[i][1] = Math.min(cost[i-1][0], cost[i-1][2]) 
                                                            + cost[i][1];
			cost[i][2] = Math.min(cost[i-1][0], cost[i-1][1]) 
                                                            + cost[i][2];
            // 이 과정에서 개편되는 cost는 T번째 집까지 칠하는 데 드는 
            // 최소 비용이 저장될 것이다.
            // i번째를 특정 색으로 칠하는 경우, 다음 집을 칠하는 순서부터는 
            // 해당 값을 활용할 일이 없다.
            // 따라서, 새로운 공간을 만들지 않고,
            // 똑같은 공간을 갱신시켜도 문제가 없다.
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		cost = new int[N+1][3];
		
		for(int i =1;i<N+1;i++) {
			for(int j =0;j<3;j++) {
				cost[i][j] = sc.nextInt();
			}
		}
		
		dp();
		
		System.out.println(Math.min(Math.min(cost[N][0],cost[N][1]),
                                                          cost[N][2]));
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과