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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

이웃한 집과 서로 다른 색으로 N개의 집을 칠할 때, 최소의 비용을 구하는 문제이다.

하나의 예를 통해서 어떻게 풀어나갈지 알아보자.

3개의 집이 있고(N = 3) , 각 집을 칠하는 비용이 색깔 별로 다음과 같은 상황을 생각해보자. [ 빨강 , 초록 , 파랑 ]

1번집 = [ 1 , 2 , 3 ]

2번집 = [ 2 , 3 , 4 ]

3번집 = [ 3 , 4 , 5 ]

지금부터 위의 상황에서 집을 칠할건데 본인은 가장 왼쪽에 있는 집부터(번호가 작은 집 부터) 색깔을 채워넣을 것이다. 물론 ! 색깔을 채워넣을 때 그 값이 최소가 되도록 만들어 주면서 채워넣을 것이다.

가장 먼저 1번집을 칠해보자. 1번집은 어떤 조건이 붙지 않는다. 왜냐하면 1번집은 가장 처음으로 색을 칠하는 집이기 때문에, 이웃한 집과 서로 다른 색을 가져야 한다는 조건을 신경쓰지 않아도 된다.

그럼 ! 1번집을 '어떤 색' 으로 칠했다고 가정하고 넘어가보자. 빨강이 가장 최소비용이기 때문에 빨강으로 칠해보자 ! 라고 하고 싶지만, 우리가 구해야 하는 것은 "모든 집을 칠하는 비용의 최소값" 이기 때문에 지금 당장 눈앞에 있는 집을 최소 값으로 칠한다고 해서 그 값이 결과값이 될 수가 없다.

그리고 2번집으로 넘어가보자. 2번집은 1번집과는 서로 다른 색깔로 칠해야 한다. 물론 ! 3번집과도 서로 다른 색깔로 칠해야 하지만, 우리는 지금 번호가 작은 집부터 순차적으로 색을 칠하고 있기 때문에 3번 집은 아직 칠하지 않은 상태라고 생각할 수 있다. 따라서 ! 2번집 입장에서는 1번집을 칠해놓은 색깔과 다른색깔로만 칠해주면 된다.

우리는 '어떤 색'으로 1번 집을 칠해놓았다. 이 '어떤 색'이랑 다른 색깔로 칠해보자.

만약, '어떤 색' 이 빨강색이라고 가정해보자. 그럼 2번집 입장에서는 2가지 선택권이 생기게 된다. '초록색', '파랑색'

만약, '어떤 색' 이 초록색이라고 가정해보자. 그럼 2번집 입장에서는 '빨강색', '파랑색' 중 하나를 선택하게 된다.

만약, '어떤 색' 이 파랑색이라고 가정해보자. 그럼 2번집 입장에서는 '빨강색', '초록색' 중 하나를 선택하게 된다.

그럼 위의 내용들을 한번 계산해보자. 정리해보면 다음과 같아질 것이다.

- 어떤 색 = 빨강색 & 2번집 = 초록색 = 1 + 3 = 4 의 비용

- 어떤 색 = 빨강색 & 2번집 = 파랑색 = 1 + 4 = 5 의 비용

- 어떤 색 = 초록색 & 2번집 = 빨강색 = 2 + 2 = 3 의 비용

- 어떤 색 = 초록색 & 2번집 = 파랑색 = 2 + 4 = 6 의 비용

- 어떤 색 = 파랑색 & 2번집 = 빨강색 = 3 + 2 = 5 의 비용

- 어떤 색 = 파랑색 & 2번집 = 초록색 = 3 + 3 = 6 의 비용

위와 같이 6가지 경우를 만들어 낼 수가 있다. 아까도 말했듯이, "어떤 색 = 초록색 & 2번집 = 빨강색 이 가장 비용이 적게 드니까 이 경우로 문제를 진행해보자 !" 라고 하면 안된다. 눈 앞에 보이는 결과값이 최소라고 해서, 전체의 결과값이 최소라는 보장이 없기 때문이다.

그럼 1번집을 '어떤 색' 으로 칠했다고 말했으니 , 2번집을 '어떤 색2' 로 칠했다고 가정하자.

그리고 3번집을 칠해보자.

3번집 같은 경우에는 2번집만 신경을 쓰면 된다. 그럼 다음과 같은 경우들이 존재한다.

- 어떤 색2 = 빨강색 & 3번집 = 초록색

- 어떤 색2 = 빨강색 & 3번집 = 파랑색

- 어떤 색2 = 초록색 & 3번집 = 빨강색

- 어떤 색2 = 초록색 & 3번집 = 파랑색

- 어떤 색2 = 파랑색 & 3번집 = 빨강색

- 어떤 색2 = 파랑색 & 3번집 = 초록색

위와 같은 경우들이 있다. 그럼 저 중에서 가장 최소값을 골라내기만 하면 된다.

그럼 이제 위의 내용들을 정리하면서 하나의 정형화된 식을 도출해보자.

현재 내가 'a번째 집' 이라고 가정하면, 우리는 a - 1번, a + 1번 집과는 서로 다른 색으로 집을 칠해야 하지만, 앞에서 부터 색을 칠한다고 가정해보면, a - 1번 집이랑만 서로 다른 색깔로 칠해주면 된다.

그리고 a - 1번 집이랑 서로 다른 색으로 칠해야 하는데, 이는 '어떤 색' 이랑 서로 다른 색깔로 칠해주면 된다는 것을 의미한다.

그런데 위에 내용에서 보면 색깔이 쳐져 있는 문구들만 다시한번 읽어보자. 하나의 '어떤 색'에 대해서 a번째 집이 가질 수 있는 경우는 2가지가 존재한다.

a - 1번째 집을 '어떤 색'으로 칠했다고 가정했을 때, a번째 집을 칠할 수 있는 경우는 2가지 씩 존재한다는 것이다.

'어떤 색'이 빨강색일 때도 2가지, '어떤 색'이 파랑색일 때도 2가지, '어떤 색'이 초록색일 때도 2가지.

우리는 각 색깔 별로 최소값들을 저장해주면서 색을 칠해주면 된다.

왜 색깔 별로 최소값을 저장해주어야 할까?? 계속 말했듯이, 눈 앞에 보이는 결과가 최소값이라고 해서 전체 결과과 최소값이라는 보장이 없기 때문이다.

그래서 본인은 하나의 배열을 통해서 위의 내용들을 관리해 주었다. 바로 , DP[][3] 이라는 int 형 2차원 배열이다.

DP[a][0] = b 의 의미는 "a번째 집을 빨강색으로 칠했을 때, 드는 최소비용은 b 원입니다."

DP[a][1] = b 의 의미는 "a번째 집을 초록색으로 칠했을 때, 드는 최소비용은 b 원입니다."

DP[a][2] = b 의 의미는 "a번째 집을 파랑색으로 칠했을 때, 드는 최소비용은 b 원입니다." 를 의미한다.

그럼 위의 값을 구체적으로 한번 구해보자.

DP[a][0] 의 값은 , a번째 집을 빨강색으로 칠했을 때의 최소비용을 구하는 것이다.

즉 ! 이 경우에는 "a - 1번째 집을 초록색으로 칠한 경우와 a - 1번째 집을 파랑색으로 칠한 경우" 2가지 경우가 존재한다.

그 중 ! 최소값을 저장해 주면 되는 것이다.

즉 ! DP[a][0] = Min(DP[a - 1][1] , DP[a - 1][2]) 가 된다. 물론, 이 결과값에, a번째 집을 빨강색으로 칠하는데 드는 비용을 더해주어야 한다. 그래야, a번째 집을 빨강색으로 칠할 때의 최소비용을 구할 수 있게 된다.

다른 색깔도 마찬가지이다.

DP[a][1] = Min(DP[a - 1][0] , DP[a - 1][2])

DP[a][2] = Min(DP[a - 1][0] , DP[a - 1][1])

로 표현할 수가 있다.

이를 점화식으로 사용해서 정답을 도출할 수 있다. 그런데 ? 정답은 뭘까 ??

우리가 N번째 집까지 다 구했다고 가정해보자. 즉, 우리는 DP[N][0] , DP[N][1] , DP[N][2] 이 3개의 값을 모두 구했다고 가정해보자. 정답은 ?? 저 3가지 값 중에서 가장 최소값이 전체의 최소값, 즉 ! 정답이 되는 값이다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N;
int Cost[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++) cin >> Cost[i][0] >> Cost[i][1] >> Cost[i][2];
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        DP[i][0] = Min(DP[i - 1][1] + Cost[i][0], DP[i - 1][2] + Cost[i][0]);
        DP[i][1] = Min(DP[i - 1][0] + Cost[i][1], DP[i - 1][2] + Cost[i][1]);
        DP[i][2] = Min(DP[i - 1][0] + Cost[i][2], DP[i - 1][1] + Cost[i][2]);
    }
    cout << Min(Min(DP[N][0], DP[N][1]), DP[N][2]) << 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;
}