[백준] 1149번: RGB거리 - C/C++

문제 출처

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

1149번: RGB거리

---

실버 1 다이나믹 프로그래밍 문제이다.

 

규칙은 

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

다음과 같다.

그럼 결국 n번 집의 색과 n-1번 집의 색이 다르기만 하면 된다는 소리다.

 

따라서 점화식은

dp[n][0] = rgb[n].red + min(dp[n-1][1], dp[n-1][2])

dp[n][1] = rgb[n].green + min(dp[n-1][0], dp[n-1][2])

dp[n][2] = rgb[n].blue + min(dp[n-1][0], dp[n-1][1])

이 된다.

 

dp[n-1]에는 각각의 색깔에 대한 최솟값이 들어있기 때문에

마지막으로 세가지 색깔을 전부 비교하여 그중 가장 최솟값을 출력하면 된다.

 

 

 

#풀이 

#include<iostream>
#include<vector>
#include<queue>
#define MAX 1000
#define INF __INT32_MAX__
using namespace std;
typedef struct RGB{
    int r;
    int g;
    int b;
}rgb_t;
int main()
{
    vector <rgb_t> rgb;
    int dp[MAX+1][3]={0,};
    int N,ans=INF;
    cin>>N;
    for(int i=0,a,b,c;i<N;i++){
        cin>>a>>b>>c;
        rgb.push_back({a,b,c});
    }
    dp[0][0] = rgb[0].r;
    dp[0][1] = rgb[0].g;
    dp[0][2] = rgb[0].b;

    for(int i=1;i<N;i++){
        dp[i][0] = rgb[i].r + min(dp[i-1][1], dp[i-1][2]);
        dp[i][1] = rgb[i].g + min(dp[i-1][0], dp[i-1][2]);
        dp[i][2] = rgb[i].b + min(dp[i-1][0], dp[i-1][1]);
    }
    for(int i=0;i<3;i++){
        ans = min(ans, dp[N-1][i]);
    }
    cout<<ans;
    return 0;
}