[백준 1149번 : 실버1] RGB거리 (DP/Java)

이번 문제는 내가 어떻게 문제를 풀어야 할지는 감이 약간 잡혔지만 구현 하는 부분에서 애를 먹어 결국 약간의 힌트를 보고 문제를 풀었다.

 

 

 

문제를 살펴보자.

 

 

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

 

입력

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

출력

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

 

 

 

 

 

 

문제 접근 방법

 

나는 이번 문제를 처음에는 최소값을 구하는 방식으로 접근을 했었다.

 

83	40	26
49	60	57
13	89	99

 

그렇게 되면 

26 - 49 - 89 를 택하게 된다.

하지만 이 방식으로 하게 되면 최소값이 될수 없다.

 

그것보다 더 최소값인 방식은

26 - 60 - 13 이 된다.

 

따라서 우리는 문제를 접근할때 당시의 최소값이 아닌 누적으로 최소값을 구해야 한다.

 

따라서 내가 본 힌트 부분이 아래와 같다.

 

dp[3][3]일때

초기값	초기값	초기값
dp[1][0] = Math.min(dp[0][1], dp[0][2]) +cost[1][0]	dp[1][1] = Math.min(dp[0][0], dp[0][2]) +cost[1][1]	dp[1][2] = Math.min(dp[0][0], dp[0][1]) +cost[1][2]
dp[2][0] = Math.min(dp[1][1], dp[1][2]) +cost[2][0]	dp[2][1] = Math.min(dp[1][0], dp[1][2]) +cost[2][1]	dp[2][2] = Math.min(dp[1][0], dp[1][1]) +cost[2][2]

 

따라서 이렇게 하게되면 마지막 위치에는 각자의 위치에서 가질수 있는 최소값을 가질수 있다.

 

그래서 해당 식을 소스로 하면 아래와 같다.

 

	public int findMin(int i, int j,int[][] dp, int[][] rgb) {
		// TODO Auto-generated method stub
		if(dp[i][j] == 0) {
			if(j == 0) {
				dp[i][j] = Math.min(findMin(i-1,1,dp,rgb), findMin(i-1,2,dp,rgb))+rgb[i][j];
				return dp[i][j];
			}else if(j == 1) {
				dp[i][j] = Math.min(findMin(i-1,0,dp,rgb), findMin(i-1,2,dp,rgb))+rgb[i][j];
				return dp[i][j];
			}else if(j == 2) {
				dp[i][j] = Math.min(findMin(i-1,0,dp,rgb), findMin(i-1,1,dp,rgb))+rgb[i][j];
				return dp[i][j];
			}
		}
		return dp[i][j];
	}

 

 

그럼 이제 마지막 값중 가작 최소값을 가져오면 된다.

나는 그부분을 아래와 같이 표현했다.

 

		int min = Integer.MAX_VALUE;
		for(int i = 0; i<3;i++) {
			int su = a.findMin(houses-1,i,dp,rgb);
			if(min > su)
				min = su;
		}

 

 

 

그래서 전제 소스를 보면 아래와 같다.

import java.util.Scanner;

public class Run {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Run a = new Run();
		Scanner sc = new Scanner(System.in);
		
		int houses = sc.nextInt();
		
		int[][] rgb = new int[houses][3];
		
		for(int i = 0; i<houses;i++) {
			for(int j = 0; j<3;j++) {
				rgb[i][j] = sc.nextInt();
			}
		}
		
		int[][] dp = new int[houses][3];
		dp[0][0] = rgb[0][0];
		dp[0][1] = rgb[0][1];
		dp[0][2] = rgb[0][2];
		
		//3의 가장 작은 값을 빼줘야 함
		int min = Integer.MAX_VALUE;
		for(int i = 0; i<3;i++) {
			int su = a.findMin(houses-1,i,dp,rgb);
			if(min > su)
				min = su;
		}
		System.out.println(min);
	}

	public int findMin(int i, int j,int[][] dp, int[][] rgb) {
		// TODO Auto-generated method stub
		if(dp[i][j] == 0) {
			if(j == 0) {
				dp[i][j] = Math.min(findMin(i-1,1,dp,rgb), findMin(i-1,2,dp,rgb))+rgb[i][j];
				return dp[i][j];
			}else if(j == 1) {
				dp[i][j] = Math.min(findMin(i-1,0,dp,rgb), findMin(i-1,2,dp,rgb))+rgb[i][j];
				return dp[i][j];
			}else if(j == 2) {
				dp[i][j] = Math.min(findMin(i-1,0,dp,rgb), findMin(i-1,1,dp,rgb))+rgb[i][j];
				return dp[i][j];
			}
		}
		return dp[i][j];
	}
}

 

 

 

 

느낀점

 

1. 누적된 최소값을 구할때는 항상 그 이전 단계에서 구할수 있는 값중에서 Math.min()을 사용해 값을 구한뒤

합하는 방법을 구하는 쪽으로 생각해야 한다.

 

 

 

참고 사이트

https://st-lab.tistory.com/128

[백준] 1149번 : RGB거리 - JAVA[자바]