[BOJ_C++] 17404번 : RGB거리 2

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>
#include <string>

using namespace std;
int dp[1001][3];
int cost[1001][3];
#define MAX 10000000000

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

    
    int n, result; cin >> n;
    for(int i=1;i<=n;i++)
        cin >> cost[i][0] >> cost[i][1] >> cost[i][2];

    result = MAX;
    for (int color = 0; color < 3; color++) {
        for (int i = 0; i < 3; i++) {
            if (i == color)dp[1][i] = cost[1][i];
            else dp[1][i] = MAX;
        }
        for (int i = 2; i <= n; i++) {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
            dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + cost[i][2];
        }
        for (int i = 0; i < 3; i++)
            if (i != color) result = min(result, dp[n][i]);
    }
    
    printf("%d", result);

    return 0;
}

• 첫 번째 집의 색을 고정한 뒤 비용을 계산하고 그 중 최소값을 찾아줄 것이다.
• 첫 번째 집을 칠할 색이 아닌 나머지 색은 MAX값을 주어 계산하지 않도록 한다.
• 각 색을 칠하는 경우의 수를 모두 구한 뒤 첫 번째 집과 마지막 집의 색이 겹치지 않을 때 최소값을 result에 저장한다.
• 이와 같은 방법으로 3가지(첫 번째 집을 칠할 수 있는 경우의 수)를 모두 진행하고 result를 구하여 출력하고 프로그램을 종료한다.

결과