[백준 알고리즘/BOJ/C++] 1149 RGB거리

 

 

↑ 결국 똑같은 색의 집이 연속해서 나올 수 없다는 말을 복잡하게 설명...

​

배열로 입력받을 것이니 행, 열로 보자

​

(1) 같은 열의 수는 연속해서 더할 수 없다 (각 열이 빨강, 초록, 파랑을 의미하기 때문에 연속할 수 없다)

(2) 어떤 루트로 가야 최솟값이 될지 모른다 (1행에서 최솟값을 골라도 최종적으로 제일 작다는 보장은 없다)

(3) 다다음 행은 고려할 필요가 없다 (기준이 되는 행과 그 다음 행만 비교하면 됨)

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int cost[1000][3], n;
    int dp[1000][3]; //각 루트마다 값을 저장해줄 배열
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
    }
 
    dp[0][0] = cost[0][0];
    dp[0][1] = cost[0][1];
    dp[0][2] = cost[0][2];
 
    for (int i = 1; i < n; i++) {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
    }
 
    cout << min({ dp[n - 1][0], dp[n - 1][1], dp[n - 1][2] });
}

 

입력값을 저장할 배열(cost) 외에 각 루트마다 값을 저장해줄 배열을(dp) 하나 더 만들어줌

​

dp[i][0] = i번째 집을 R, i-1번째 집을 R 제외 제일 싼 색으로 칠했을 때 비용의 합

dp[i][1] = i번째 집을 G, i-1번째 집을 G 제외 제일 싼 색으로 칠했을 때 비용의 합

dp[i][2] = i번째 집을 B, i-1번째 집을 B 제외 제일 싼 색으로 칠했을 때 비용의 합

​

​

처음엔 i번째 집을 기준으로 i+1번째 집을 어떤색으로 칠할지 정하려고 했으나..

i+1번째 집을 무슨 색으로 칠했는지 따로 저장해야하고..이것 저것 코드가 줄줄 늘어나서 역으로 계산했다

​

이 때 못참고 또 답 찾아봄..거의 다 풀어놓고 솔루션 검색해서 찝찝하게 끝내기 달인ㅎㅋ