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

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

1149번: RGB거리

풀이

이번 문제는 dp 문제로 설명이 너무 어렵게 되어있다. 

간단하게 설명하자면 문제의 조건은 "인접한 집끼리 색이 겹치면 안된다."이다.

 

모든 dp문제는 점화식만 찾으면 쉽게 해결할 수 있다.

1번 예제를 보면서 점화식을 찾아보겠다.

1번 예제

1번 예제에서 최소값만 찾아서 누적합을 하면 다음과 같다.

최소값만 찾아서 진행했더니 문제의 조건 "인접한 집끼리 색이 겹치면 안된다." 를 위반한다.

결론은 최소값만 찾아서 진행하는 게 아닌 모든 경로의 경우의 수를 다 따져봐야한다는 뜻이다. 

 

이 문제에서 경우의 수는 총 3가지이다.

 

1. N-1번 집을 빨간색으로 선택했을 경우

Math.min(cost[i-1][2], cost[i-1][3]) + cost[i][1];

2. N-1번 집을 초록색으로 선택했을 경우

Math.min(cost[i-1][1], cost[i-1][3]) + cost[i][2];

3. N-1번 집을 파란색으로 선택했을 경우

Math.min(cost[i-1][1], cost[i-1][2]) + cost[i][3];

3가지의 경우 중에 값이 더 적은 값을 선택하면서 dp 배열을 채워가면 문제를 쉽게 해결할 수 있다.

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        int N = Integer.parseInt(br.readLine());
        int[][] cost = new int[N+1][N+1];
        int[] dp = new int[N+1];
		
        for (int i=1; i<N+1; i++) {
            st = new StringTokenizer(br.readLine());
            cost[i][1] = Integer.parseInt(st.nextToken()); // 빨간색
            cost[i][2] = Integer.parseInt(st.nextToken()); // 초록색
            cost[i][3] = Integer.parseInt(st.nextToken()); // 파란색
        }
		
        dp[0] = 0;
        dp[1] = Math.min(cost[1][1], Math.min(cost[1][2], cost[1][3]));
		
        for (int i=2; i<N+1; i++) {	
            cost[i][1] = Math.min(cost[i-1][2], cost[i-1][3]) + cost[i][1];
            cost[i][2] = Math.min(cost[i-1][1], cost[i-1][3]) + cost[i][2];
            cost[i][3] = Math.min(cost[i-1][1], cost[i-1][2]) + cost[i][3];
			
            dp[i] = Math.min(cost[i][1], Math.min(cost[i][2], cost[i][3]));
        }
		
        System.out.println(dp[N]);
    }
}