백준 1149번: RGB거리

문제 출처: https://www.acmicpc.net/problem/1149

세 이웃 간 색깔이 달라야 하는 것이 아니라, 두 이웃 간 색깔이 다르면 된다. (ex: 빨강 초록 빨강)

DP(Dynamic Programming)로 푼다.

cost[0][0] = 26  // 집1을 빨강으로 칠할 때 비용 

cost[0][1] = 40  // 집1을 초록으로 칠할 때 비용 

cost[0][2] = 83  // 집1을 파랑으로 칠할 때 비용 

cost[1][0] = min(cost[0][1], cost[0][2]) + cost[1][0]  // 집1을 초록과 파랑으로 칠할 때 비용 중 최솟값과, 집2를 빨강으로 칠할 때 비용

cost[1][1] = min(cost[0][0], cost[0][2]) + cost[1][1]  // 집1을 빨강과 파랑으로 칠할 때 비용 중 최솟값과, 집2를 초록으로 칠할 때 비용

cost[1][2] = min(cost[0][0], cost[0][1]) + cost[1][2]  // 집1을 빨강과 초록으로 칠할 때 비용 중 최솟값과, 집2를 파랑으로 칠할 때 비용

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        int[][] cost = new int[N][3];
 
        for(int i=0 ; i<N ; i++){
            String[] input = reader.readLine().split(" ");
            cost[i][0] = Integer.parseInt(input[0]);
            cost[i][1] = Integer.parseInt(input[1]);
            cost[i][2] = Integer.parseInt(input[2]);
        }
 
        for(int i=1 ; i<N ; i++){
        // cost[i][0] = 집 i을 빨강으로 칠할 때 비용 + 집 i-1을 빨강을 제외한 나머지 색들로 칠할 때의 비용 중 최소값
            cost[i][0] += Math.min(cost[i-1][1], cost[i-1][2]); // 49 += (40, 83)
            cost[i][1] += Math.min(cost[i-1][0], cost[i-1][2]); // 60 += (26, 83)
            cost[i][2] += Math.min(cost[i-1][0], cost[i-1][1]); // 57 += (26, 40)
        }
 
        Arrays.sort(cost[N-1]);
        System.out.println(cost[N-1][0]);
    }
}