백준 1149, RGB 거리

1. 문제

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

1149번: RGB거리

2. 문제요약

1. N개의 집을 R,G,B의 색상 중 하나로 칠하여야 합니다.
2. 각각의 집을 칠하는 R,G,B 색상이 주어졌을 때 모든 집을 칠하는 최소 비용을 계산하여야 합니다.
3. 색상을 칠하는 규칙은 다음과 같습니다.
   1. 1번집과 2번집의 색은 달라야 합니다.
   2. N번집과 N-1번집의 색은 달라야 합니다.
   3. i(2<=i<=N-1)번 집은 i-1, i+1번 집의 색과 달라야 합니다.

3. 예제 입력1 수행과정

예제 입력1의 데이터 샘플을 표로 나타내면 다음과 같습니다.

N=3	R	G	B
1번집	26	40	83
2번집	49	60	57
3번집	13	89	99

처음 문제를 풀었을때 직관적으로 생각했던 해결방법은 1번집을 칠하는 3개 비용 중 최소비용인 색상을 선택하고 2번집부터 N번째 집까지 색칠 규칙을 준수하면서 최소 비용을 누적하면 그것이 N개의 집을 칠하는 최소비용합계라고 생각하였습니다. 아래 표는 제가 생각한 과정입니다.

N=3	R	G	B
1번집	26	40	83
2번집	49	60	57
3번집	13	89	99

실제로 위와 같이 선택하게 되면 26+57+13=96의 값을 얻어 예제 입력1의 출력과 동일한 값을 얻게 됩니다. 하지만 위와 같은 해결방법은 잘못된 해결방법임을 다른 예제를 통해서 알게 되었습니다. 예를 들면 아래와 같은 입력이 되었다고 가정하겠습니다.

N=3	R	G	B
1번집	1	100	200
2번집	1	300	400
3번집	301	302	1

위의 입력에서 제가 처음 생각한 해결방법대로 한다면 1+300+1=302의 값을 얻게 될 것입니다. 하지만 정답은 100+1+1=102의 값입니다. 즉, 1번집부터 최소 비용을 선택하는 방법은 해결방법이 아님을 알게 되었습니다.

 

위 문제를 해결하기 위해서는 첫번째 집이 3가지 경우의 수로써 각각 R, G, B로 칠하기 시작하면서 전체 집을 칠하는 비용들 중 제일 최소 값을 선택하면 됩니다.

 

예를 들어 위의 입력에서 첫번째 집이 각각 R, G, B를 칠한다고 가정하면 선택과정은 아래와 같습니다.

1. 1번집이 R을 선택하는 경우 : 1 + 300 + 1 = 302
2. 1번집이 G를 선택하는 경우 : 100 + 1 + 1 = 102
3. 1번집이 B를 선택하는 경우 : 200 + 1 + 1 = 202

위의 결과에서 302, 102, 202 중 최소값은 102이므로 1번집이 G을 선택하는 경우에 모든 집을 칠하는 최소 비용이 됩니다.

 

위의 3가지 경우를 고려하여 i번째 집까지의 최소 비용을 구하는 점화식은 다음과 같습니다.

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

2차원 배열 dp의 의미는 지금까지 색칠하는데 드는 최소 비용을 의미합니다. 예를 들어 dp[3][0]에서 1차원 배열은 집을 의미하며 2차원 배열은 해당 집을 칠하는 색깔(R=0,G=1,B=2)를 의미합니다. 즉, dp[3][0] 배열은 3번째집까지 칠하는 최소 비용을 의미하며 3번째 집은 R=0을 선택했을때 3번째 집 포함 최소 비용을 의미합니다.

 

위의 점화식을 해석하자면 dp[i][0]은 i번째 집이 R을 선택하고 i번째집까지 칠하는 최소 비용을 의미합니다. arr[i][0]은 i번째 집의 R의 색상 비용이고 dp[i-1][1], dp[i-1][2]는 i-1번째 집까지의 G, B로 색칠할때 둘중 최소 비용을 선택하는 것입니다.

 

4. 소스코드

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

public class Main {
	static int[][] arr;
	static long[][] dp;

	public static long recursion(int i, int color)
	{
		if(i==0)
		{
			return 0;
		}
		
		if(color==0)
		{
			return dp[i][0] = arr[i][0] + Math.min(
					dp[i-1][1]==0 ? recursion(i-1,1) : dp[i-1][1],
					dp[i-1][2]==0 ? recursion(i-1,2) : dp[i-1][2]
					); 
			
		}
		else if(color==1)
		{
			return dp[i][1] = arr[i][1] + Math.min(
										dp[i-1][0]==0 ? recursion(i-1,0) : dp[i-1][0],
										dp[i-1][2]==0 ? recursion(i-1,2) : dp[i-1][2]
										);
		}
		else
		{
			return dp[i][2] = arr[i][2] + Math.min(
										dp[i-1][0]==0 ? recursion(i-1,0) : dp[i-1][0],
										dp[i-1][1]==0 ? recursion(i-1,1) : dp[i-1][1]
										);
		}	
	}
	
	public static long solution(int n)
	{	
		return Math.min(Math.min(recursion(n,0), recursion(n,1)), recursion(n,2));
	}
	
	public static void main(String args[]) throws NumberFormatException, IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		arr = new int[n+1][3];
		dp = new long[n+1][3];
		
		for(int i=1;i<=n;i++)
		{
			int[] rgb = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			arr[i] = rgb;
		}		
		System.out.println(Main.solution(n));
	}
}

 

References

https://m.blog.naver.com/occidere/220785383050