[C++] 1149: RGB거리

🖍️ 겪은 문제

• DFS 백트래킹으로 풀었다가 시간 초과가 발생했다.

🔍 해결 방법

• 알고리즘 보기를 눌러보고 DP로 풀어야 한다는 점을 알게됐다. 그래서 DP로 풀이했는데 너무 오랜만에 DP문제 혼자 성공해서 뿌듯해서 로그를 남긴다 🥹
• 근데, DP로 풀어야하는 문제인지를 어떻게 알 수 있을까?
  • 각 집마다 3가지 색상을 선택할 수 있음. 최악의 경우에 3^1000이 됨.
  • int의 범위가 -2^31 ~ 2^31 - 1 이므로, 엄~~~~청 큰 수다.

📇 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};

struct Price {
    int r;
    int g;
    int b;
};

enum COLOR {
    RED,
    GREEN,
    BLUE,
    COLOR_MAX
};

int N;
vector<Price> prices;
int dp[1001][COLOR_MAX];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    for (int i=0; i<N; i++) {
        int r, g, b;
        cin >> r >> g >> b;
        prices.push_back({r, g, b});
    }

    dp[0][RED] = prices[0].r;
    dp[0][GREEN] = prices[0].g;
    dp[0][BLUE] = prices[0].b;

    for (int i=1; i<N; i++) {
        dp[i][RED] = min(dp[i-1][GREEN] + prices[i].r,
            dp[i-1][BLUE] + prices[i].r);
        dp[i][GREEN] = min(dp[i-1][RED] + prices[i].g,
            dp[i-1][BLUE] + prices[i].g);
        dp[i][BLUE] = min(dp[i-1][RED] + prices[i].b,
            dp[i-1][GREEN] + prices[i].b);
    }

    int minPrice = min({dp[N-1][RED], dp[N-1][GREEN], dp[N-1][BLUE]});

    cout << minPrice << '\n';

    return 0;
}