[BOJ/백준 1149][C++] RGB거리

문제

https://www.acmicpc.net/problem/1149

백준 1149

 

문제 내용

n개의 집을 빨/초/파 3가지 색으로 칠하려고 한다.

각각의 집을 3가지 색으로 칠할 때의 비용이 주어졌을 때, 모든 집을 칠하는 최소 비용을 구하면 된다.

단, 인접한 집은 서로 색이 달라야 한다.

 

문제 풀이

dp로 문제를 풀 수 있다.

dp[i][0]은 i번째 집을 칠하기까지 필요한 비용 (단, i번째 집은 빨간색)
dp[i][1]은 i번째 집을 칠하기까지 필요한 비용 (단, i번째 집은 초록색)
dp[i][2]은 i번째 집을 칠하기까지 필요한 비용 (단, i번째 집은 파란색)

이런 식으로 설정하고 문제를 풀면 쉽게 해결할 수 있다.

 

코드

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

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

    int dp[n + 1][3]; // 빨, 초, 파
    dp[1][0] = arr[1][0];
    dp[1][1] = arr[1][1];
    dp[1][2] = arr[1][2];

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

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