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

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

 

dp 예제 문제이다. n개의 지붕을 칠할때 rgb 세값중 한 값을 선택하여 칠할 수 있다.

하지만 칠하는 값이 매 n회차마다 다르고 지붕의 색은 이전과 이후색과 겹칠 수 없다. 즉 rr gg bb 이런식으로 겹치지만 않으면 된다. 

 

3
26 40 83
49 60 57
13 89 99

입력 예제이다.

 

n값으로는 3이 들어왔고

집값은 각각 rgb값이다.

 

1회차에 가장 저렴한 빨간색으로 칠한다 가정하자. dp[1]은 26이다.

dp[2]는 rr을 연속으로 칠하지 못하므로 26 + 57 = 83이다.

dp[3]은 다시 r로 칠하면 83 + 13 = 96 출력값 또한 96이다.

 

dp의 값을 결정할 때 dp[i-1]과 그 값을 제외한 최소값 또는 i회차의 최솟값과 dp[i-1]의 그 값을 제외한 최솟값 중 작은 값을 선택하면 될듯하다.

 

이런식으로 코드를 짜보았더니 최소값을 비교하는 과정에서 불필요한 연산이 반복되었다.

 

 

 

i번째의 집을 칠하는 색깔에 따라 최솟값을 나누어 저장해준다면 이전 연산을 반복하지 않아도 된다.

 

즉, dp를 3차원 배열로 선언하고 (dp[1001][3]) dp[1001][0]에는 i번째집이 빨강일때 1일때는 초록일때, 2일때는 파랑일 때 각각 저장해 주었다. 

 

#include <iostream>
#include <algorithm>
#define MAX 1001
using namespace std;
long long dp[MAX][3] = { 0, };
 
int main(int argc, char* argv[])
{
    int n;
    int cost[3];
    cin >> n;
    cin >> dp[0][0] >> dp[0][1] >> dp[0][2];
    for (int i = 1;i < n;i++) {
        cin >> cost[0] >> cost[1] >> cost[2];
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[1];
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[2];
    }
 
    cout << min(min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]) << '\n';
 
    return 0;
}

 

천천히 생각하면 이해하기는 쉽다. 하지만 아직 떠올리기는 어렵다. 

 

이제 dp의 구조나 사용방법을 알것같은 문제이다.