[백준 1149번] RGB거리 (DP기본 / C++)

 

코드보면 dp가 참 짧은 라인 수인데,,

생각해 내기가 너무 힘들더라.

맨처음엔 그리디인 것 같아서 풀었는데, 반례가 있어서 납득했다.

예를들어 극단적으로

2

1 10 100

1 100 200

이런 경우만 따져봐도 1번 집에서 Greedy하게 비용 1을 선택하면 2번 집에서 101, 201을 가지게 되는 반면

1번 집에서 10을 선택하면 2번집에서 1을 선택해서 11의 비용을 가질 수 있다.

그러므로 그리디는 이러한 경우때문에 성립이 불가하다.

 

아래 코드에서는 dp배열을 ary와 동일한 사이즈로 만들어두고 채워나간다.

그림으로 따지면 이렇다.

i번째 집에 칠할 수 있는 비용은 

이전까지 칠해온 비용 + 현재 집에서 칠하는 비용(Ri, Gi, Bi)인데,

R-R , G-G, B-B를 연속으로 칠하는 것은 불가능 하므로 

DP[Ri]의 경우 i-1의 G,B중 min값을 취하고 현재의 Ri를 더하면 되는 식이다.

 

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
vector<string> v;
map<string,int> m;
int ary[1001][3];
int dp[1001][3];
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N,tmp;
    cin >> N;
    
    for(int i = 1; i<= N; i++)
    {
        for(int j =0; j< 3; j++)
        {
            cin >> tmp;
            ary[i][j] = tmp;
        }
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + ary[i][0];
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + ary[i][1];
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + ary[i][2];
    }
    cout << min(dp[N][0], min(dp[N][1], dp[N][2])) << endl;

}