<Algorithm> 77. 1149번 RGB거리

1. 1149번 RGB거리

• DP문제 문제별 0.5초 밖에 주지 않는 것을 보고 DP로 풀어야한다는 것을 알았는데 생각보다 식세우기가 쉽지 않은 문제

• DP를 어느정도 파악했다고 생각했는데 DP 생각보다 더 다양한 것 같다. 

• 그동안 푼 문제들은 bottom up 이나 top down 방식으로 풀었는데 이거는 임의의 기준점을 세워서 푸는 문제라 생각된다.

• 힌트를 보고도 못푼 이유가 맨처음집에서 R을 선택 , G를 선택, B를 선택 하는 경우로 접근하려고 했는데 이 경우는 맨처음집에서 R을 선택해서 그리디하게 식을 만들어 보았다.

  dp[i+1][0] = Math.min(arr[i][1], arr[i][2]) + dp[i-1][0];  문제점은 i-1번째가 기준이 되기 때문에 dp[0]에 들어가는 것이 중복될 수 있다.

• i라는 기준점을 세우고 i-1 값을 판단하여 점화식을 세워서 풀 수 있었다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int[][] arr;
    static int res = 0;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());        
        arr = new int[N][3];
        int dp[][] = new int[N][3];
        StringTokenizer st;
        for(int i = 0; i < N; i ++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dp[0][0] = arr[0][0];
        dp[0][1] = arr[0][1];
        dp[0][2] = arr[0][2];
        
        for(int i = 1; i < N; i++) {
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + arr[i][0];
            // i번째가 R을 선택하는 경우, i-1번째가 G아니면 B를 선택해야됨 -> 둘중의 최소값 
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + arr[i][1];
            // i번쨰가 G를 선택하는 경우
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + arr[i][2];
            // i번째가 B를 선택하는 경우
        }
        
        System.out.println(Math.min(Math.min(dp[N-1][0], dp[N-1][1]),dp[N-1][2]));
    }
}

참고 & 출처  https://m.blog.naver.com/occidere/220785383050