[1149번] RGB거리 JAVA☕

www.acmicpc.net/problem/1149

1149번: RGB거리

알고리즘 [접근 방법]

풀이조건을 설명하자면 다음과 같다.
일단 각각의 집을 색칠해야하고, 색의 종류는 3가지가 주어진다 ( 빨강, 초록, 파랑 )
그리고 각 집마다 해당 색을 칠하는 비용이 주어진다. 그리고 전체 집을 색칠할 때 최소 비용을 구하는 것이다.

이때 중요한 점이라면 인접한 집끼리는 색이 겹치면 안된다는 점이다.
예를들어 3번 집에 초록색을 칠한다면, 2번집과 4번집은 초록색을 칠할 수 없다.
이러한 조건으로 인해 비용을 구할 때 최소값만을 찾아서 하면 틀리게 된다.

만약 각 집마다 최소값을 찾아 누적합을 하면 다음과 같은 일이 생긴다.

---

 

1번 집 최소값=1

---

인접한 집끼리는 같은 색을 칠할 수 없으므로 2번집의 초록색과 파란색 중

최소값을 찾아 누적합. 즉 103+ 1

---

이전 집이 초록색이었으므로 빨간색 집과 파란색 집 중 최소값을 누적합. 즉 100+104

---

즉, 위와 같이 하면 출력은 204가 되겠지만 이게 정답일 수 있겠지만 답은 아니다.

사실 정답은 100(1번집 초록) + 1(2번집 빨강) + 1(3번집 초록)인 102가 정답이다.

각 집별 최소값이 아닌 아래 그림과 같은 빨간색 칸을 선택해야 올바른 정답이 된다.

결과적으로 각 집의 최소값을 찾아 누적합을 구하는 것이 아닌 모든 경로의 경우의 수를 찾아서 최종적으로 작은 누적합을 찾아야 한다.

 

각 집의 비용을 Cost라고 할 때, 이를 한 단계씩 적어보면 다음과 같다.

(이때 min은 두 개의 값 중 최소값을 의미하며 +=은 누적합이다.)

 

즉, 점화식으로 본다면 N에 대하여 세 가지 케이스에 대해 다음과 같다.

 

1. 빨강일 경우
   Cost[N][0] = min( Cost[N-1][1], Cost[N-1][2] ) + Cost[N][0]
2. 초록일 경우
   Cost[N][1] = min( Cost[N-1][0], Cost[N-1][2] ) + Cost[N][1]
3. 파랑일 경우
   Cost[N][2] = min( Cost[N-1][0], Cost[N-1][1] ) + Cost[N][2]

이제부터는 동적계획법으로 풀이하기만 하면 된다.

기본적으로 이전의 문제들(01타일, 피보나치 등)과 같은 알고리즘을 사용하면 된다.

다만 3가지 케이스를 이용해야하니 Cost[][] 배열과, 탐색하면서 누적합을 저장할 DP[][] 함수를 만들면 된다. 그리고나서 위 점화식을 이용하여 재귀함수로 구성한 뒤, 해당 배열을 아직 탐색하지 않았다면 재귀를 해주고, 그 외의 경우는 DP배열의 값을 반환해주면 된다.

 

각 비용은 자연수로 입력된다고 하니 DP배열을 -1로 초기화 해줄 필요없이 탐색하지 않은 경우를 초기값(0)으로 사용하면 된다.

int[][] Cost = new int[N][3];	// 이미 입력값들로 초기화가 되었다고 가정
 
int[][] DP = new int[N][3];
 
// DP의 첫번째 값(집)은 각 색상비용의 첫번째 값으로 초기화
DP[0][Red] = Cost[0][Red];	
DP[0][Green] = Cost[0][Green];
DP[0][Blue] = Cost[0][Blue];
 
	
static int Paint_cost(int N, int color) {
 
	// 만약 탐색하지 않은 배열이라면
	if(DP[N][color] == 0) {
			
		// color의 색에 따라 이전 집의 서로 다른 색을 재귀호출하여 최솟값과 현재 집의 비용을 더해서 DP에 저장한다
		if(color == Red) {
			DP[N][Red] = Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue)) + Cost[N][Red];
		}
		else if(color == Green) {
			DP[N][Green] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Blue)) + Cost[N][Green];
		}
		else {
			DP[N][Blue] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Green)) + Cost[N][Blue];
		}
			
	}
		
	return DP[N][color];
}

이렇게 짜면 이후 다른 색에 대하여 탐색을 할 때 이전에 탐색했던 값의 경우 더이상 재귀호출 해줄 필요 없이 바로 해당 DP의 인덱스 값을 재활용하면 되기 때문에 동적계획법에도 알맞은 알고리즘일 것이다.

 

이렇게 하나의 함수를 만들고 Paint_cost(N, Red), Paint_cost(N, Green), Paint_Cost(N, Blue) 을 호출하여 해당 반환 값 중 최솟값을 출력해주면 된다.

 

풀이

- 방법 1 : [재귀 + Scanner]

import java.util.Scanner;
 
public class Main {
	
	final static int Red = 0;
	final static int Green = 1;
	final static int Blue = 2;
	
	static int[][] Cost;
	static int[][] DP;
	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
        
		Cost = new int[N][3];
		DP = new int[N][3];
		
		for(int i = 0; i < N; i++) {
			Cost[i][Red] = in.nextInt();
			Cost[i][Green] = in.nextInt();
			Cost[i][Blue] = in.nextInt();
		}
		
		// DP의 첫번째 값(집)은 각 색상비용의 첫번째 값으로 초기화
		DP[0][Red] = Cost[0][Red];
		DP[0][Green] = Cost[0][Green];
		DP[0][Blue] = Cost[0][Blue];
		
		
		System.out.print(Math.min(Paint_cost(N- 1, Red), Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue))));
	}
	
	static int Paint_cost(int N, int color) {
		
		// 만약 탐색하지 않은 배열이라면
		if(DP[N][color] == 0) {
			
			// color의 색에 따라 이전 집의 서로 다른 색을 재귀호출하여 최솟값과 현재 집의 비용을 더해서 DP에 저장한다
			if(color == Red) {
				DP[N][Red] = Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue)) + Cost[N][Red];
			}
			else if(color == Green) {
				DP[N][Green] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Blue)) + Cost[N][Green];
			}
			else {
				DP[N][Blue] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Green)) + Cost[N][Blue];
			}
			
		}
		
		return DP[N][color];
	}
}

- 방법 2 : [반복문 + BufferedReader]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	final static int Red = 0;
	final static int Green = 1;
	final static int Blue = 2;
 
	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][3];
 
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
 
			Cost[i][Red] = Integer.parseInt(st.nextToken());
			Cost[i][Green] = Integer.parseInt(st.nextToken());
			Cost[i][Blue] = Integer.parseInt(st.nextToken());
 
		}
 
		// 1부터 N-1까지 각 i별 i-1의 서로 다른 색상 중 최솟값을 누적하여 더한다.  
		for (int i = 1; i < N; i++) {
			Cost[i][Red] += Math.min(Cost[i - 1][Green], Cost[i - 1][Blue]);
			Cost[i][Green] += Math.min(Cost[i - 1][Red], Cost[i - 1][Blue]);
			Cost[i][Blue] += Math.min(Cost[i - 1][Red], Cost[i - 1][Green]);
		}
 
		System.out.println(Math.min(Math.min(Cost[N - 1][Red], Cost[N - 1][Green]), Cost[N - 1][Blue]));
	}
 
}

모든 경우의 수 중 최솟값을 더해나가면서 구하는 방식이지만 동적계획법이긴 하다.