[백준/C++] 1149번: RGB거리

문제

풀이

3*N의 2차원 배열을 선언하였고, 각각의 행은 R, G, B를 나타낸다.

i번째의 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다는 조건은 결국 연속한 세 집의 색이 같으면 안된다는 조건과 같다.

dp[0][i] 행을 예시로 설명하면, i번째에 들어갈 최솟값은 [현재 집을 빨간색으로 칠하는 비용 + (이전 집을 초록색으로 칠하는데까지 필요한 비용, 이전 집을 파란색으로 칠하는데까지 필요한 비용, 이전 집을 빨간색으로 칠하는데까지 필요한 비용 중 최솟값)] 이다.

그런데 이전 집을 빨간색으로 칠하는데까지 필요한 비용엔 연속한 두 집을 빨간색으로 칠하는게 포함되어 연속한 세 집을 빨간색으로 칠하게 되버리니, 수정이 필요하였다.

전전 집을 빨간색으로 칠하는데까지 필요한 비용 + (이전 집을 초록색으로 칠하는데 필요한 비용, 이전 집을 파란색으로 칠하는데 필요한 비용중 최솟값)으로 작성하여 해결하였다.

코드

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

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

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

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

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

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

    return 0;
}