[백준] 1149번 - RGB거리

문제 >

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력 >

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

 

출력 >

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

 

해결방법 > 

동적 계획법으로 해결

 

s[i][0] : i번째 집을 빨강으로 칠했을 때 최소비용

s[i][1] : i번째 집을 초록으로 칠했을 때 최소비용

s[i][2] : i번째 집을 파랑으로 칠했을 때 최소비용

 

s[i][0] = min(s[i-1][1], s[i-1][2]) + a[i][0];

s[i][1] = min(s[i-1][0], s[i-1][2]) + a[i][1];

s[i][2] = min(s[i-1][0], s[i-1][1]) + a[i][2];

 

즉 i번 째 집을 특정 색으로 칠했을 때 최소비용은 i번째 집을 i에서 칠한 색을 제외한 두 가지 색상으로 칠했을 때 나오는 최소비용 중 더 작은 값과 i번째 집을 칠하는데 들어간 비용이 된다.

 

따라서 위와 같은 점화식을 이용해 n번째 집까지 총 비용을 구한다.

 

[JAVA]

package baekjoon;

import java.util.*;

public class BOJ_1149{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] a = new int[n][3];
		int[][] s = new int[n][3];
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < 3; j++) {
				a[i][j] = sc.nextInt();
				if(i == 0) {
					s[i][j] = a[i][j];
				}
			}
		}
		
		for(int i = 1; i < n; i++) {
			s[i][0] = Math.min(s[i-1][1], s[i-1][2]) + a[i][0];
			s[i][1] = Math.min(s[i-1][0], s[i-1][2]) + a[i][1];
			s[i][2] = Math.min(s[i-1][0], s[i-1][1]) + a[i][2];
		}
		
		System.out.println(Math.min(s[n-1][0], Math.min(s[n-1][1], s[n-1][2])));
	}
}

 

문제링크 >

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

1149번: RGB거리