[백준] 1149 RGB거리

www.acmicpc.net/problem/1149

1149번: RGB거리

2020-11-07

---

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

public class Main1149 {
	public static int N, arr[][], dp[][];
	
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine().trim());
		N = Integer.parseInt(st.nextToken());
		
		arr = new int[N][3];
		dp = new int[N][3];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j = 0; j < 3; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dp[1][0] = arr[1][0] + Math.min(arr[0][1], arr[0][2]);
		dp[1][1] = arr[1][1] + Math.min(arr[0][0], arr[0][2]);
		dp[1][2] = arr[1][2] + Math.min(arr[0][0], arr[0][1]);
		
		for(int i = 2; i < N; 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]);
		}
		System.out.println(Math.min(dp[N-1][0], Math.min(dp[N-1][1],dp[N-1][2])));
	}
}

힌트를 받아서 풀었다.

 

먼저, 각 집의 빨강, 초록, 파랑으로 칠할 때 드는 비용 값은 arr[N][3] 에 저장했다. 

 

1. 2번째 집을 먼저 빨강으로 칠할 때의 최소 비용은 1번째 집을 초록 또는 파랑으로 칠할 때의 최솟값 + 2번째 집을 빨강으로 칠할 때 드는 비용이 된다. 이것을 dp 라는 배열에 저장했다. 같은 방법으로 2번째 집을 초록, 파랑으로 칠할 때 드는 비용도 계산할 수 있다.

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

이 값을 초기값으로 저장해둔다. 입력 값에서 집의 수(N) 2<= N <= 1000 이라는 전제가 있다. 만약 N이 2이면 초기값이 모든 집을 칠하는 최소 비용이 될 것이다.

 

2. N이 2보다 크면 현재 집을 빨강으로 칠할 때의 최소 비용은 그 전의 집을 초록 또는 파랑으로 칠할 때의 최솟값과 현재 집을 빨강으로 칠할 때의 최소 비용을 합한 값이 된다.

for(int i = 2; i < N; 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]);
}

3. 마지막으로 마지막 집까지 칠했을 때 빨강, 초록, 파랑 기준으로 가장 최소 비용을 출력하면 된다.

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