문제

https://www.acmicpc.net/problem/1149

풀이

연속된 같은 열을 선택하지 않고 각 행에서 비용을 하나씩 정한 합의 최솟값을 구하는 문제다.

좀 더 쉽게 말하자면 한 행마다 비용을 하나씩 정해야 하는데 그 전에 정한 열의 비용은 선택하지 않아야 한다.

완전 탐색을 하면 시간초과가 나기 때문에
DP를 이용하여 해결하자.

dp[i][Red] = cost[i][Red] 
			+ Math.min(dp[i-1][Blue], dp[i-1][Green]);
            
dp[i][Blue] = cost[i][Blue] 
			+ Math.min(dp[i-1][Red], dp[i-1][Green]);

dp[i][Green] = cost[i][Green]
			+ Math.min(dp[i-1][Blue], dp[i-1][Red]);

현재 색깔을 선택한다면 그 전의 다른 색깔들을 골랐던 경우에 추가적으로 합을 더해간다.

최종적으로 각 색을 선택했을 때의 경우 중 가장 최솟값을 출력해주면 된다.

CODE

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader((new InputStreamReader(System.in)));
        int n = Integer.parseInt(br.readLine());
        int[][] homes = new int[n][n];
        int[][] dp = new int[n + 1][n + 1];
        
        for (int i = 0; i < n; ++i) {
            String[] tokens = br.readLine().split(" ");
            for (int j = 0; j < tokens.length; ++j) {
                homes[i][j] = Integer.parseInt(tokens[j]);
            }
        }

        for (int i = 1; i <= n; ++i) {
            dp[i][0] = homes[i - 1][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = homes[i - 1][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = homes[i - 1][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
        }

        int ans = Math.min(dp[n][0], Math.min(dp[n][1], dp[n][2]));

        System.out.println(ans);
    }

}