[백준] 1149번 : RGB 거리

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

1149번: RGB거리

 

완전탐색 문제인 줄 알았는데, dp문제이다. 

완전 탐색으로 풀 경우 O(3^N) 시간복잡도이고, 좀 더 단순한 방법을 생각해야 통과할 수 있다.

구하는 것은 최소 비용이므로 부분 문제의 해가 전체 문제의 해가 될 수 있다. 즉, dp로 풀 수 있다.

dp의 경우 시간복잡도는 O(N)이다.

DP 생각 타이밍

완전탐색의 시간복잡도가 클 경우 / 1번부터 N번까지 차례대로 탐색하는데 그리디가 아닌 경우 => dp로 풀자.

 

코드

#include <bits/stdc++.h>
using namespace std;
int n;
int cost[1004][3], dp[1004][3];

int main(){
    //1. 입력받기
    cin >> n;
    for (int i=0;i<n;i++)
        for (int j=0;j<3;j++) 
            cin >> cost[i][j];
    //2. dp 수행
    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];
    }
    //3. 정답 출력
    cout << min({dp[n-1][0], dp[n-1][1], dp[n-1][2]});
}