1149. RGB거리

1. 해결방법

• Dynamic Programming
• DP 문제의 해결방법은 "큰 문제를 작은 문제로 나누기이다. 즉, 1)DP[][] 값 모두 구하고 2) answer 찾기"이다.

2. Solution

// Dynamic Programming
#include <iostream>

#define MAX 1000 + 1
#define endl "\n"

using namespace std;

int N, answer;
int MAP[MAX][3];
int DP[MAX][3];

int Min(int A, int B) {if(A < B) return A; return B;}

void Input()
{
    cin >> N;
    for(int i = 1; i <= N; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            cin >> MAP[i][j];
        }
    }

    // 초기화
    DP[0][0] = DP[0][1] = DP[0][2] = 0;
    MAP[0][0] = MAP[0][1] = MAP[0][2] = 0;
}


void Solution()
{
    for(int i = 1; i <= N; i++)
    {
        DP[i][0] = Min(DP[i-1][1], DP[i-1][2]) + MAP[i][0];
        DP[i][1] = Min(DP[i-1][0], DP[i-1][2]) + MAP[i][1];
        DP[i][2] = Min(DP[i-1][0], DP[i-1][1]) + MAP[i][2];
    }

    answer = Min(Min(DP[N][0], DP[N][1]), DP[N][2]);
    cout << answer << endl;
}


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

    Input();
    Solution();

    return 0;
}