[백준] 1149번: RGB거리

문제링크 : https://www.acmicpc.net/problem/1149

 

문제풀이

처음엔 주어진 테스트 케이스를 보고도 이해가 잘 안갔는데, 동적 계획법으로 풀 수 있는 문제였다.

 

문제와 같은 경우, 아래와 같이 칠을 하면 최솟값 96이 나온다.

 

집 a부터 차례로 색을 칠한다고 하면, 칠할 수 있는 경우는 아래와 같다.

b집을 빨강으로 칠한다고 하면, 옆집인 a는 초록 또는 파랑으로 칠할 수 밖에 없다.

 

따라서 b를 빨강으로 칠했을 때 최소비용은

a를 초록으로 칠했을 때 드는 비용, a를 파랑으로 칠했을 때 드는 비용 중 최소 비용을 더한 값과 같다.

 

마지막 집 c를 빨강으로 칠했을 때 최소비용은

색칠한 칸들의 네가지 경우 중 가장 최소비용을 더한 값과 같다.

 

따라서, i번째 집에 오기까지 최소비용을 미리 차례로 구해놓으면,

N번째 집까지 칠했을 때의 최소비용을 쉽게 구할 수 있다.

 

 

소스코드

package baekjoon;

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

public class P1149 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[][] arr = new int[N][3];
		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			StringTokenizer st = new StringTokenizer(s);
			for (int j = 0; j < 3; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 1; i < N; i++) {
			arr[i][0] += Math.min(arr[i - 1][1], arr[i - 1][2]);
			arr[i][1] += Math.min(arr[i - 1][0], arr[i - 1][2]);
			arr[i][2] += Math.min(arr[i - 1][0], arr[i - 1][1]);
		}
		
		System.out.println(Math.min(arr[N - 1][0], Math.min(arr[N - 1][1], arr[N - 1][2])));
		
		br.close();
	}
}