[동적 계획법] 백준 1149번 RGB거리(Java)

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

1149번: RGB거리

📚 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 떄, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

 

예제 입력	예제 출력
3 26 40 83 49 60 57 13 89 99	96
3 1     100 100 100 100 100 1     100 100	102
6 30 19 5 64 77 64 15 19 97 4   71 57 90 86 84 93 32 91	208
8 71 39 44 32 83 55 51 37 63 89 29 100 83 58 11 65 13 15 47 25 29 60 66 19	253

 

📝 문제 해결

서로 인접한 집의 색은 겹치면 안되므로 첫번째 집부터 최솟값을 찾은 다음, 두번째 줄에서 첫번째 색상을 제외한 것 중에 최솟값을 구하여 더해주면서 dp에 저장해주면 된다.

 

• 테이블 정의하기
  dp[i] = i번째 집일 때 집을 칠하는 최소 비용
• 점화식 찾기
  i번째 집이 빨강일 때(0), i-1번째 집이 초록(1) 혹은 파랑(2) 중 최솟값과 빨강일 때의 값을 더해준다.

dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + r

 

	r	g	b
1	26	40	83
2	49	60	57
3	13	89	99

 

1) i = 1일 때,

dp[0][0] = 0	dp[0][1] = 0	dp[0][2] = 0
dp[1][0] = 26	dp[1][1] = 40	dp[1][2] = 83

2) i = 2일 때,

dp[0][0] = 0	dp[0][1] = 0	dp[0][2] = 0
dp[1][0] = 26	dp[1][1] = 40	dp[1][2] = 83
dp[2][0] = Math.min(40, 83) + 49	dp[2][1] = Math.min(26, 83) + 60	dp[2][2] = Math.min(26, 40) + 57

2) i = 3일 때,

dp[0][0] = 0	dp[0][1] = 0	dp[0][2] = 0
dp[1][0] = 26	dp[1][1] = 40	dp[1][2] = 83
dp[2][0] = 89	dp[2][1] = 86	dp[2][2] = 83
dp[3][0] = Math.min(86, 83) + 13 = 96	dp[3][1] = Math.min(89, 83) + 89 = 172	dp[3][2] = Math.min(89, 86) + 99 = 185

 

💻 코드

import java.util.*;

public class BOJ1149 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[][] dp = new int[N + 1][3];

        for (int i = 1; i <= N; i++) {
            int r = sc.nextInt();
            int g = sc.nextInt();
            int b = sc.nextInt();

            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + r;
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + g;
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + b;
        }
        
        System.out.println(Math.min(dp[N][0], Math.min(dp[N][1], dp[N][2])));
    }
}