[BOJ/백준][Gold4] 17404: RGB거리2 (C++)

www.acmicpc.net/problem/17404

17404번: RGB거리 2

 

 

[난이도] Gold4

[유형] DP

 

[풀이]

마지막 집은 첫번째 집과 색이 달라야 하므로 첫번째 집의 색을 기억해야 한다. 첫번째 집의 색을 R,G,B각각 고정했을 때의 비용의 최솟값중 가장 작은 것이 정답이다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,cost[1000][3],dp[1000][3],INF=1e9;
int ans=INF;
int sol(int s){
    for(int i=0;i<N;i++) for(int j=0;j<3;j++) dp[i][j] = INF;
    dp[0][s] = cost[0][s];
    int ret = INF;
    for(int i=1;i<N;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                if(j!=k) dp[i][j] = min(dp[i][j],dp[i-1][k]+cost[i][j]);
            }
        }
    }
    for(int i=0;i<3;i++) if(i!=s) ret = min(ret,dp[N-1][i]);
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) 
        for(int j=0;j<3;j++) scanf("%d",&cost[i][j]);
    for(int i=0;i<3;i++){
        int ret = sol(i);
        ans = min(ans,ret);
    }
    printf("%d",ans);
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/17404.cpp