[백준 1149] RGB거리

 

 

예제의 값으로 풀이 방법을 서술해보겠다.

 

 

 

	R	G	B
dp[0][i] = a[0][i]	26	40	83

dp 배열의 첫번째 인덱스에는 입력받은 값을 받는다.

 

 

	R	G	B
dp[0][i]	26	40	83
dp[1][i]	49 + 40	60 + 26	57 + 26

색상은 연속으로 칠할 수 없으므로 다른 색상 중 최소값을 받아 더한다.

 

 

	R	G	B
dp[0][i]	26	40	83
dp[1][i]	49 + 40	60 + 26	57 + 26
dp[2][i]	13 + 60 + 26	89 + 57 + 26	99 + 60 + 26

마찬가지로 채워준다.

 

 

---

dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + a[i][0];

dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + a[i][1];

dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + a[i][2];

---

위 표의 결과대로 만든 점화식이다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[][] = new int[n][3];
        int dp[][] = new int[n][3];
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<3; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        
        dp[0][0] = a[0][0]; dp[0][1] = a[0][1]; dp[0][2] = a[0][2];
        for(int i=1; i<n; i++) {
            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + a[i][0];
            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + a[i][1];
            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + a[i][2];
        }
        
        System.out.println(min(min(dp[n-1][0], dp[n-1][1]), dp[n-1][2]));
        sc.close();
    }
    
    public static int min(int a, int b) {
        return a < b ? a : b;
    }
    
}