[BOJ] 1149. RGB거리 (C++)

문제

1번 집부터 N번 집이 순서대로 있다. 집은 RGB 중 하나의 색으로 칠해야 한다.

각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 최솟값은?

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

생각할 것

3가지 조건을 모두 반영해보자

표를 만들어서 풀었다

집 번호 / RGB	R	G	B
0	26	40	83
1	40(0번집 G) + 49(1번집 R) = 89, 83(0번집 B) + 49(1번집 R) = 132 따라서 89 기록	26 + 60, 83 + 60 => 86	26 + 57, 40 + 57 => 83
2	86 + 13, 83 + 13 => 96 ( 마지막 집의 최솟값이 정답)	89 + 89, 83 + 89 => 172	89 + 99, 86 + 99 => 185

1. 가장 먼저 0번째 집은 RGB 비용을 그냥 적는다.

2. 다음 집 부터는 표에 해당하는 컬러를 제외한 이전 집 비용 + 현재 집의 해당 컬러 비용을 더해주었다. 

3. 그리고 최솟 값을 비교해 표에 기록한다.

4. 위의 과정을 반복한 뒤, 마지막 집의 RGB 중 가장 적은 값이 정답이 된다.

 

*min_element를 쓸 때 헤더에 #include <algorithm> 추가하는 것 잊지말기

코드

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

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

    int N;
    cin >> N;

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

    for (int i = 1; i < N; i++) { // 집
        for (int j = 0; j < 3; j++) { // 입력할 RGB
            int num = INT_MAX;
            for (int k = 0; k < 3; k++) { // 이전값과 더할 RGB
                if (j != k) {
                    num = min(num, dp[i-1][k] + dp[i][j]);
                }
            }
            dp[i][j] = num;
        }
    }

    cout << *min_element(dp[N-1].begin(), dp[N-1].end());

    return 0;
}