[알고리즘] RGB 거리

구현 방식

• 다이나믹 프로그래밍으로 아래와 같은 식을 세운다.

i 번째 집을 C 색(R/G/B) 으로 칠할 때 0~i 번째 집까지의 최소 색칠 비용  = 
	i 번째 집 C 색 색칠 비용 + Min( i 번째 집을 C 이외의 색 으로 칠할 때 0~i-1 번째 집까지의 최소 색칠 비용)

• 예로 acc[i][R] = w[i][R] + min(acc[i-1][G] , acc[i-1][B]) 와 같이 될 것이다.

#include <bits/stdc++.h>

using namespace std;

enum class Color;
void solution(int N, vector<map<Color, int>>& colorWeight);
int DP(int N, vector<map<Color, int>>& colorWeight);

enum class Color
{
    Red = 0,
    Green = 1,
    Blue = 2,
};

void solution(int N, vector<map<Color, int>>& colorWeight) {
    int result = DP(N, colorWeight);
    cout << result;
}


int DP(int N, vector<map<Color, int>>& colorWeight)
{
    auto accMinWeight = vector<map<Color, int>>(N);
    accMinWeight[0][Color::Red] = colorWeight[0][Color::Red];
    accMinWeight[0][Color::Green] = colorWeight[0][Color::Green];
    accMinWeight[0][Color::Blue] = colorWeight[0][Color::Blue];

    for (int i = 1; i < N; ++i)
    {
        accMinWeight[i][Color::Red] = colorWeight[i][Color::Red] + 
                                        min(accMinWeight[i - 1][Color::Green],
                                            accMinWeight[i - 1][Color::Blue]);
        accMinWeight[i][Color::Green] = colorWeight[i][Color::Green] +
                                        min(accMinWeight[i - 1][Color::Red],
                                            accMinWeight[i - 1][Color::Blue]);
        accMinWeight[i][Color::Blue] = colorWeight[i][Color::Blue] +
                                        min(accMinWeight[i - 1][Color::Red],
                                            accMinWeight[i - 1][Color::Green]);
    }

    return min(accMinWeight[N - 1][Color::Red],
            min(accMinWeight[N - 1][Color::Green], 
                accMinWeight[N - 1][Color::Blue]));
}