[백준-1149]-[다이나믹프로그래밍] - RGB 거리

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

이문제를 이해하는데 오래걸렸지만 한번 이 문제를 이해하니 쉽게 이해하지 못한 내 자신이 한심해졌다.

문제의 설명을 보게 되면 3개의 행에 입력받는 N개의 열이 존재하고  이웃끼리는 같은 색을 할 수 없다고 한다. 

이웃의 조건은 i번째 기준 i-1, i+1 이 기준이라하니 아래 위로는 같은 색을 선택 할수 없다고 하는조건이다. 

그냥 같은 색으로 칠하면 안되나 빡친다.

	R	G	B
1 번째	26	40	83
2 번째	49	60	57
3번째	13	89	99

이문제를 풀기 위해서는 R,G,B의 색상 최소 값을 가지고 있는 배열이 필요하다. (int[] price  index의 0 = R, 1 = G, 2 = B 를 나타낸다.)

문제를 푸는 과정은 1번째 ~ N 번째까지 반복을 하면서 현재 입력받은 색상 정보와 이전에 입력받은 자기 이외의 두 색의 최소값을 합하면 된다. 

예를 들어 2번째 집에 R,G,B 각각의 색상을 칠할때  최소값을 계산해보자

R :  min( 1번째 G 값, 1번째 B 값) + 현재 입력받은 R 값 --> 89

G :  min( 1번째 R 값, 1번째 B 값) + 현재 입력받은 G 값 --> 86

B :  min( 1번째 R 값, 1번째 G 값) + 현재 입력받은 B 값 --> 83

2번째 집까지만 칠 했을때 R, G, B 의 값중 최소값은 83이고 이 값이 2번째 까지의 최소값이다. 

그럼 3번째 집을 색칠해보면서 예제 입력의 출력값과 계산한 값이 같은지 보자

R :  min( 2번째 G 값, 2번째 B 값) + 현재 입력받은 R 값 --> 96

G :  min( 2번째 R 값, 2번째 B 값) + 현재 입력받은 G 값 --> 172

B :  min( 2번째 R 값, 2번째 G 값) + 현재 입력받은 B 값 --> 185

오!! 3번째에서는  최소값이 96이 나온다. 예제 출력과 같다. 

그럼 저 풀이로 점화식을 만들어 보자. 

마을의 색상 정보는 정수형 이차원 배열 arr[N+1][3] 에 저장한다.

각 단계별 색상의 최소값을 담는 정수형 이차원 배열 arr[N+1][3] 도 생성하고 각 단계별 최소값을 저장한다.

R : min ( price[i-1][1],  price[i-1][2] ) + arr[i][0] 

G : min ( price[i-1][0], price[i-1][2] ) + arr[i][1]

B : min ( price[i-1][0], price[i-1][1] )  + arr[i][2]

이제 점화식도 구했으니 코딩을 해보자.

소스

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class E_1149 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int NUM = Integer.parseInt(br.readLine());
        
        int[][] arr = new int[NUM+1][3];
        int[][] price = new int[NUM+1][3];
        
        for(int i=1; i <= NUM; i++) {
                st = new StringTokenizer(br.readLine());
                // 현재 색상 가격을 입력받자
                arr[i][0] = Integer.parseInt(st.nextToken());
                arr[i][1] = Integer.parseInt(st.nextToken());
                arr[i][2] = Integer.parseInt(st.nextToken());
                
                // 현재단계 최소값을 구하자
                price[i][0] = Math.min(price[i-1][1], price[i-1][2]) + arr[i][0];
                price[i][1] = Math.min(price[i-1][0], price[i-1][2]) + arr[i][1];
                price[i][2] = Math.min(price[i-1][0], price[i-1][1]) + arr[i][2];
        }
        
        System.out.println(Math.min(price[NUM][0], Math.min(price[NUM][1], price[NUM][2])));
    }
 
}