[백준] Silver I. RGB 거리

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

 

사용 알고리즘

• 다이나믹 프로그래밍

코드

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

public class Main {
    static int n;
    static int [] r = new int[1002];
    static int [] g = new int[1002];
    static int[] b = new int[1002];
    static int [][] dp = new int[1002][3];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for(int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            r[i] = Integer.parseInt(st.nextToken());
            g[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
        }

        dp[1][0] = r[1];
        dp[1][1] = g[1];
        dp[1][2] = b[1];

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

        System.out.println(Math.min(Math.min(dp[n][0],dp[n][1]),dp[n][2]));

    }
}

 

 

회고

 

 

테이블 정의

d[i][0]: i번째 집까지 칠할때 최솟값, i번째 집은 빨강
d[i][1]: i번째 초록
d[i][2]: i번째 파랑

 

점화식

d[k][0] = min(d[k-1][1], d[k-1][2]) + r[k]

 

문제에서 N번째 집의 색은 N-1번째 색과 같지 않아야 한다는 조건이 있다. 

 

마지막 집을 빨강으로 칠한다고 할 때, 그전의 집(N-1)은 파랑과 초록으로 칠했을 때의 total을 계산하면 되고 그 중에서 최솟값을 찾는다. 

 

그렇게 마지막 집을 빨강, 초록, 파랑을 칠할 때의 케이스를 각자 나눠서 계산하면 되고 최종적으로 이들의 최솟값을 구해주면 된다.

 

2차원 배열로 dp를 선언한 이유는 색깔 정보를 저장해야 하기 때문에 그렇게 선언했다.