[Java] 백준 17404번: RGB거리 2 - DP(다이나믹 프로그래밍)

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

17404번: RGB거리 2

 

문제

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

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

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

---

 

전형적인 DP로 접근하면 풀 수 있는 문제이다.

 

먼저, 각각의 집에 대한 비용을 입력받아 저장해준다.

cost[i][j]에서 j는 0(빨강), 1(초록), 2(파랑)이다.

for(int i=1; i<=N; i++){
    st = new StringTokenizer(br.readLine());
    for(int j=0; j<3; j++){
        cost[i][j] = Integer.parseInt(st.nextToken());
    }
}

 

우선 경우의 수를 첫 집의 색깔로 나눈다. 빨강, 초록, 파랑 3가지 경우이다.

첫 번째 집이 k일 경우 첫 번째 집이면서 k색에 해당하는 비용을 저장해주고, 다른 색의 집은 최대값으로 설정해준다.

이때, 최대값을 Integer.MAX_VALUE로 설정할 경우, 밑에 값을 더하는 과정에서 오버플로우가 발생할 수 있으므로 주의해준다.

for(int i=0; i<3; i++){
    if(k == i) dp[1][i] = cost[1][i];
    else dp[1][i] = 1000 * 1000;
}

 

첫 번째 값을 설정한 이후에, dp 식을 일반화시켜 구현하면 된다.

문제에서의 조건은 이웃한 집의 색이 달라야 하는 것이다.

빨강일 경우, 앞에 초록, 파랑이 올 수 있는데 둘 중에 최소 비용으로 구하고, 현재 i번째의 빨강집의 비용을 추가해준다.

초록일 경우, 앞에 빨강, 파랑이 올 수 있을 것이다.

파랑일 경우, 앞에 빨강, 초록이 올 수 있을 것이다.

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

 

그럼 dp[N][0], dp[N][1], dp[N][2] 의 값이 나올 것이다.

이 값들을 비교하여 최소값을 구하면 된다.

for(int i=0; i<3; i++){
    if(i != k)
        min = Math.min(min, dp[N][i]);
}

 

마지막으로, 위의 내용을 첫번째 집이 빨강, 초록, 파랑일 경우 3가지로 나누어서 진행하면 된다.

for문으로 k변수를 선언하여 3번을 반복하였다.

for(int k=0; k<3; k++){
    for(int i=0; i<3; i++){
        if(k == i) dp[1][i] = cost[1][i];
        else dp[1][i] = 1000 * 1000;
    }
    for(int i=2; i<=N; i++){
        dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
        dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
        dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
    }

    for(int i=0; i<3; i++){
        if(i != k)
            min = Math.min(min, dp[N][i]);
    }
}

 

 

소스 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());

		int[][] cost = new int[N+1][3];
		int[][] dp = new int[N+1][3];

		for(int i=1; i<=N; i++){
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<3; j++){
				cost[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int min = Integer.MAX_VALUE;

		for(int k=0; k<3; k++){
			for(int i=0; i<3; i++){
				if(k == i) dp[1][i] = cost[1][i];
				else dp[1][i] = 1000 * 1000;
			}
			for(int i=2; i<=N; i++){
				dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
				dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
				dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
			}

			for(int i=0; i<3; i++){
				if(i != k)
					min = Math.min(min, dp[N][i]);
			}
		}

		System.out.println(min);
	}
}