백준 1149 - RGB거리 (c++)

백준 1149 - RGB거리

문제 링크

생각 및 접근

• 처음에 예제 입력 값이 무엇인지 헷갈렸지만, 각 집마다 색깔을 칠하는 가격이 달랐던 것이다.
• dp[i][j]
  • i번째 집까지 색칠했고, i번째 집에는 j의 색깔로 칠했을 때 비용의 최솟값을 저장한다.
  • 색깔은 총 3가지고, 집의 범위는 1000개까지 이므로 dp[1001][3]로 선언하였다.
  • dp[i][0]를 구하려고 할 때, 이전 집(i - 1번째 집)에서 칠한 색깔은 1 또는 2여야 하므로 min(dp[i - 1][1] + arr[i][0], dp[i - 1][2] + arr[i][0]);와 같이 점화식을 세워볼 수 있겠다.
  • dp[i][1], dp[i][2]는 위와 동일한 방식으로 아래와 같은 점화식을 세울 수 있다.
    • dp[i][1] = min(dp[i - 1][0] + arr[i][1], dp[i - 1][2] + arr[i][1]);
    • dp[i][2] = min(dp[i - 1][0] + arr[i][2], dp[i - 1][1] + arr[i][2]);

코드

#include <bits/stdc++.h>
using namespace std;

int n, arr[1001][3], dp[1001][3];

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    }

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

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

채점 결과