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

작성일 | In
골드 IV 골드 IV

문제

RGB거리 2

풀이

맨 처음 빨간색, 초록색, 파란색을 칠한 경우로 나누어서 풉니다.
최소 비용을 저장한 배열을 cost라고 합시다.
cost[c1][c2]는 맨 처음 칠한 색은 c2이고, 지금 칠한 색은 c1일때 최소 비용입니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

constexpr int RED = 0;
constexpr int GREEN = 1;
constexpr int BLUE = 2;
constexpr int INF = 1e9;


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

    int n;
    cin >> n;

    vector<vector<int>> cost(3, vector<int>(3, INF));
    cin >> cost[RED][RED] >> cost[GREEN][GREEN] >> cost[BLUE][BLUE];

    for (int i = 1; i < n; i++) {
        int red_cost, green_cost, blue_cost;
        cin >> red_cost >> green_cost >> blue_cost;

        vector<vector<int>> new_cost(3, vector<int>(3, INF));
        for (int i = 0; i < 3; i++) {
            new_cost[RED][i] = min(cost[GREEN][i], cost[BLUE][i]) + red_cost;
            new_cost[GREEN][i] = min(cost[RED][i], cost[BLUE][i]) + green_cost;
            new_cost[BLUE][i] = min(cost[RED][i], cost[GREEN][i]) + blue_cost;
        }
        cost = new_cost;
    }

    int ans = INF;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i == j) continue;
            ans = min(cost[i][j], ans);
        }
    }
    cout << ans;
}

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