[PS] BOJ1149 RGB거리 ( DP ) With Java

1149번: RGB거리

 

 

◎ 문제풀이 

 

처음에 문제를 잘못 접근하여 푸는데 시간이 걸렸다. 

 

이웃한 집과 같은 색상이면 안 되고 비용을 최소로 하는 문제이다. 그래서 정말 단순하게 생각했다. dp[n]이 n번째 집까지 색칠하는데 걸리는 최소비용이라면, 이는 dp[n-1]에서 이웃하지 않는 색상 중 최솟값을 더하면 구할 수 있다고 생각했다.  ( 그리디 관점으로 생각했다. ) 그러나 이런 생각은 모든 경우를 고려하지 않은 풀이이다. 이번 문제는 최적해를 구하는 문제가 아니다. 모든 경우의 수를 시간제한 안에 고려해야 한다. ( DP 관점으로 풀어야 한다. )

 

n-1번째 집은 R, G ,B로 칠해질 수 있다. n-1번째 집을 G로 칠할 때, 최소비용이라고 가정하자. 그렇다고 n번째 집을 R과 B 중 하나로 칠한다고 최소비용이 되는 것이 아니다. ( Greedy 관점으로 접근하면 안된다. ) n-1번째 집을 G로 칠할 때 최소비용이든 아니든 n번째에서 어떤 색상을 칠하느냐에 따라 최소비용이 달라질 수 있다. 

 

다시 말해,

n-1번째 집을 B로 칠하는 것이 당장은 최소비용이 아닐지라도 n번째 집에 G를 칠할 때, 최소비용이 될 수 있다는 의미이다. R,G,B 비용이 고정되어 있다면 n-1번째에서 최적해를 예상할 수 있겠지만 고정되어 있지않고 회차마다 변하므로 모든 경우의 수를 고려해주어야 한다.  자료구조를 R인 경우, G인 경우, B인 경우의 비용을 모두 저장하여 다음 집을 칠할 때 모든 경우를 고려 할 수 있도록 구현해야 한다. 

 

◎ 코드

import java.io.*;
import java.util.StringTokenizer;
import static java.lang.Math.min;

//BOJ1149 RGB거리
public class Dp3 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int dp[][];

        int n = Integer.parseInt(br.readLine());
        dp = new int[n+1][3];

        for(int i =1;i<=n;i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + r;
            dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + g;
            dp[i][2] = min(dp[i-1][1],dp[i-1][0]) + b;

        }

        int ans = dp[n][0];
        for(int i =0;i<3;i++){ ans = min(ans,dp[n][i]); }

        bw.write(ans+"");
        bw.flush();
        bw.close();
        br.close();
    }
}