[ 백준 1149 ] RGB거리 (C++)

백준의 RGB거리(1149) 문제이다.

( 문제 바로가기 )

( 문제를 다시 푸는 과정에서 보다 상세한 설명을 다시 포스팅 해놓았습니다. 아래의 글을 읽으셔도 무관하지만, 보다 구체적인

  설명을 원하시는 분은 아래의 링크를 타고 가시면 됩니다 ! )

  [ 백준(1149) RGB 거리 ]

( 문제를 다시 푸는 과정에서 보다 상세한 설명을 다시 포스팅 해놓았습니다. 이 글을 읽으셔도 무관하지만, 보다

  구체적인 설명을 원하시는 분들은 아래의 링크를 타고 가시면 됩니다 ! )

출처: https://yabmoons.tistory.com/15 [얍문's Coding World..]

[ 문제설명 ]

- 총 집의 수가 주어지고, 각각의 집이 빨강, 초록, 파랑으로 집을 칠할 때의 비용이 입력으로 주어진다.

- 집을 칠할 때 모든 집을 다 칠했을 때 최소 비용을 구하는 문제인데, 서로 이웃한 집은 같은 색깔로 칠할 수 없다.

- 서로 이웃한 집(x - 1, x + 1)은 같은 색깔로 칠할 수 없을 때, 최소 비용을 구하는 문제이다.

[ 문제풀이 ]

1) Dynamic Programming의 기본원리 대로 가장 작은 식부터 구해본다.

   1-1) 본인은 입력을 집은 1번집부터 N번집까지, 색깔은 0번부터 2번까지로 설정하고 같이 관리할 수 있도록 2차원 배열을

         사용했다.

   1-2) 기본적으로 각 집마다 색깔을 관리하는 MAP[][]2차원 배열과, 최소비용을 계산하는 DP[][] 2차원 배열을 선언했다.

2) MAP[a][0] = a번째 집을 빨강으로 , MAP[a][1] = a번째 집을 초록으로, MAP[a][2] = a번째 집을 파랑으로 칠할 때

   드는 비용으로 입력과 동시에 설정해 주었다.

   DP[a][b] = a번째 집을 b색깔로 칠했을 때의 최솟값을 의미한다.

   2-1) 본격적인 점화식을 구하기 전에, 초기 설정 식을 설정해보면

         MAP[0][0] = MAP[0][1] = MAP[0][2] = 0 (본인은 집 번호를 1번부터 매겼으므로, 0번집은 없으므로 값은 0)

         DP[0][0] = DP[0][1] = DP[0][2] = 0

         이 된다.

3) 점화식을 구해서 N번째 집까지 칠했을 때의 최소값을 비교해보면 되는데, N번째 집을 빨강으로 했을 때 최솟값

   파랑으로 했을 때 최솟값, 초록으로 칠했을 때의 최솟값을 모두 비교해 보아야 한다.

   1번집 부터 칠하는 과정에서 모든 집을 모든 색깔로 다 칠하는 경우의 나올 수 있는 최솟값을 설정해 주어야 한다.

   (물론 이웃한 집은 같은 색으로 칠할 수 없다는 점도 유의하면서)

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1000 + 1
 
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;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}