백준 1149 RGB거리

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

1149번: RGB거리

 

DP문제가 익숙하지않아서 정말 오랜시간 고민했다. 결국 스스로 해결하지 못하고 다른 블로그를 참고하여 문제를 해결했다. 이 문제를 계기로 동적계획법을 푸는데 2차원 배열을 이용하여 풀 수 있다는 방법도 알게되었다. 하나의 값만 저장하여 해결하는 것만 생각해서 답이 떠오르지 않았던 것이다. 이 문제의 경우 하나의 값만 저장하게 되면 지금 선택하지 못하는 색에 드는 비용이 아주 작다면 이전에 저장했던 값도 변경해주어야한다는 문제가 발생하기때문에 문제를 해결하지 못한다.

앞으로 이런 유형의 문제가 나온다면 절대 틀리지 않겠다!

 

 

풀이

 

package 동적계획법;
 
import java.io.*;
import java.util.StringTokenizer;
 
public class RGB거리 {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
 
        int[][] dp = new int[N + 1][3]; //같은 색을 연속할 수 없기 때문에 다른 두가지 색중 최소값만 더한다
        int[][] rgb = new int[N + 1][3]; //비용 저장
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                rgb[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for (int i = 0; i < 3; i++) {
            dp[1][i] = rgb[1][i];
        }
        for(int i=2;i<=N;i++){
            dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2])+rgb[i][0];
            dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2])+rgb[i][1];
            dp[i][2] = Math.min(dp[i-1][0],dp[i-1][1])+rgb[i][2];
        }
        int res = Math.min(Math.min(dp[N][0],dp[N][1]),dp[N][2]);//n번째에저장된 값들 중 최소값
        System.out.println(res);
 
    }
}