[백준/C++] 17404번 RGB거리 2

백준

 

---

🤔문제 이해

1149번 RGB거리 문제의 변형이다. 

이 문제에선 첫번째 선택한 집의 색과 마지막에 선택한 집의 색이 달라야 한다.

---

💡첫번째 아이디어

처음 선택한 색에 따라 dp 배열이 다르게 설정되어야 한다고 생각했다. 그래서 dp0, dp1, dp2 배열을 각각 선언해서 구현하였지만 왜 때문인지 4%에서 자꾸 틀렸다고 떴다 ㅠㅠ

다시 생각해보니 dp 배열이 다를 필요가 없었다!! 설명은 풀이 참조 ㄱㄱ

 

 

🔥풀이🔥

첫번째에 고를 색을 하나로 픽스해두고 1149번 RGB거리처럼 dp를 통해 가장 비용이 적게 드는 경우를 구하면 된다.

dp[i][j] : i번째 집을 칠하는 j색 (j = 0 : red / 1 : green / 2 : blue)

dp[i][0]은 dp[i-1][1]과 dp[i-1][2]중에서 더 작은 값과 i번째 집을 빨간색으로 칠하는 비용을 더한 값을 넣어준다.

dp[i][1]은 dp[i-1][0], dp[i-1][2]중에서

dp[i][2]은 dp[i-1][0], dp[i-1][1]중에서 골라 똑같이 계산해준다.

 

최종적으로 첫번째 집의 색을 고정했을 때 마지막 집의 색과 겹치지 않는다. 

왜냐? dp[1][0] = 10, dp[1][1] = MAX, dp[1][2] = MAX일 때 dp[2][0]만 MAX가 더 더해지고, dp[2][1]과 dp[2][2]는 dp[1][0]값이 더해진다. 그러고나면 dp[3][j]에는 모두 첫번째 집을 빨간색으로 칠한 경우의 비용만 들어가게 된다.

어차피 dp에는 최적의 값이 들어가기 때문에 하나의 dp배열만을 가지고 연산하고 최종적으로 dp[n][j]들끼리 비교해서 가장 작은 값을 출력해준다.

---

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int house[1002][3];
int dp[1002][3];


int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;

    int x;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> x;
            house[i][j] = x;
        }
    }

    int ans = 1000001;

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (j == i)
                dp[1][j] = house[1][j];
            else
                dp[1][j] = 1000001;
        }
        for (int j = 2; j <= n; j++) {
            dp[j][0] = min(dp[j - 1][1], dp[j - 1][2]) + house[j][0];
            dp[j][1] = min(dp[j - 1][0], dp[j - 1][2]) + house[j][1];
            dp[j][2] = min(dp[j - 1][0], dp[j - 1][1]) + house[j][2];
        }
        for (int j = 0; j < 3; j++) {
            if (j == i) continue;
            ans = min(ans, dp[n][j]);
        }
    }
    cout << ans;
}