백준 1149 - rgb거리

1️⃣ 문제 접근

처음 문제를 봤을 때 이런 생각이 들었다:

“각 집에서 최소 비용 색만 고르면 되는 거 아닌가?”

하지만 바로 막혔다.

• 이전 집 색이랑 겹치면 안됨
• 단순히 최소값만 고르면 조건을 깨버림

👉 여기서 깨달은 점:

“이 문제는 그리디가 아니라 DP다”

---

2️⃣ 내가 막혔던 포인트 😇

처음에 이런 고민을 했다:

• “방어로직을 어떻게 넣지?”
• “미리 최소값을 고르면 조건이 깨지는데?”
• “1차원으로 줄일 수 없나?”

👉 결론:

❌ 최소값 하나만 들고 가면 안 된다
✅ 경우의 수를 상태로 들고 가야 한다

---

3️⃣ 핵심 아이디어

이 문제의 본질은 이것이다:

“이전 집 색에 따라 현재 선택이 달라진다”

그래서 DP를 이렇게 정의한다:

dp[i][c] = i번째 집을 c색으로 칠했을 때 최소 비용

---

4️⃣ 점화식 (핵심)

같은 색은 선택할 수 없으므로:

dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + v[i][0]; // R
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + v[i][1]; // G
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + v[i][2]; // B

👉 “이전 색만 다르면 된다” 이게 전부다

---

5️⃣ 초기값 (중요 ⚠️)

dp[0][0] = v[0][0];
dp[0][1] = v[0][1];
dp[0][2] = v[0][2];

👉 이걸 안 넣으면 전부 0에서 시작해서 틀림

---

6️⃣ 전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;

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

    cin >> N;
    vector<vector<int>> v(N, vector<int>(3, 0));
    vector<vector<int>> dp(N, vector<int>(3, 0));

    for(int i = 0; i < N; i++){
        for(int j = 0; j < 3; j++){
            cin >> v[i][j];
        }
    }

    dp[0][0] = v[0][0];
    dp[0][1] = v[0][1];
    dp[0][2] = v[0][2];

    for(int i = 1; i < N; i++){
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + v[i][0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + v[i][1];
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + v[i][2];
    }

    cout << min({dp[N-1][0], dp[N-1][1], dp[N-1][2]}) << '\n';

    return 0;
}

---

7️⃣ 시간복잡도

• DP 계산: O(N)
• 공간복잡도: O(N)

👉 매우 효율적

---

8️⃣ 깨달은 점 💡

이 문제에서 제일 중요한 포인트는 이것이다:

“DP는 하나를 고르는 게 아니라, 상태를 유지하는 것이다”

처음에는 “최소값 하나만 들고 가면 되지 않나?”라고 생각했지만
👉 그 순간 이전 색 정보가 사라진다

그래서:

• R로 끝난 경우
• G로 끝난 경우
• B로 끝난 경우

👉 이 3개를 모두 유지해야 한다

“RGB 거리 문제는 이전 집의 색 상태를 유지하는 2차원 DP 문제이다”

👉 DP는 조건을 억지로 처리하는 게 아니라
👉 조건을 상태로 바꾸는 문제이다.