82. C++ 백준 1149 번 RGB 자세한 설명

안녕하세요 코딩하는 덕구입니다.

다이나믹 프로그래밍 문제인 1149 번 RGB C++ 자세한 설명입니다.

https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

 

먼저 1149번 정답 C++ 코드입니다.

 

R, G, B 3 가지의 색으로 집을 칠하는 비용이 주어지고,

이전에 칠했던 색으로는 연속으로 색을 칠할 수 없는 조건 속에서

모든 집을 최소한의 비용으로 칠해야 됩니다.

 

어떤 색을 먼저 칠했느냐에 따라서 최소 비용이 달라지고,

우리는 계산해보기 전까지 알 수 없으므로 3가지의 경우를 모두 계산해본 후 

그 중 최소값을 선택해야 됩니다.

 

그럼 위의 직관을 코드로 구현해봅시다.

 

모든 비용을 저장할 행렬 arr를 생성하고, 값을 입력받아 모두 저장합니다.

for (int i = 0; i < N; i++) cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

 

이제 arr에는

0번 집부터 N-1번 집까지 총 N개의 집이 R, G, B 3가지의 색으로 칠해지는 비용이 저장되어 있습니다.

 

i번째 집을 R로 칠한다고 생각해봅시다.

그렇다면 i-1 번째 집은 G 혹은 B 로 칠해져 있어야 됩니다.

 

그럼 i번째 집을 G로 칠한다고 생각해봅시다.

그렇다면 i-1 번째 집은 R 혹은 B 로 칠해져 있어야 됩니다.

 

마지막으로 i번째 집을 B로 칠한다고 생각해봅시다.

그렇다면 i-1 번째 집은 R 혹은 G 로 칠해져 있어야 됩니다.

위의 직관을 가지고 i번째 집 까지 색을 겹치지 않고 칠하는 최소 비용은

마지막 색이 R인 경우 

R + (i - 1 번째 집 까지 색을 겹치지 않고 최소한의 비용으로 칠하면서 마지막에 칠해진 색이 G 혹은 B)

arr[i][0] += min( arr[i-1][1], arr[i-1][2] );

 

마지막 색이 G인 경우

G + (i - 1 번째 집 까지 색을 겹치지 않고 최소한의 비용으로 칠하면서 마지막에 칠해진 색이 R 혹은 B)

arr[i][1] += min( arr[i-1][0], arr[i-1][2] );

 

마지막 색이 B인 경우

B + (i - 1 번째 집 까지 색을 겹치지 않고 최소한의 비용으로 칠하면서 마지막에 칠해진 색이 R 혹은 G)

arr[i][2] += min( arr[i-1][0], arr[i-1][1] );

 

가 됩니다.

 

이렇게 마지막에 칠해진 색이 R, G, B 인 경우 3가지를 반복적으로 구해서

최소값을 출력해주면 됩니다.

cout << min(min(arr[N-1][0], arr[N-1][1]), arr[N-1][2]);

 

백준 1149번 C++ 최종 코드입니다.

#include <iostream>
#define MAX 1001
int arr[MAX][3];
using namespace std;
int main(){
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

    for (int i = 1; i < N; i++){
        arr[i][0] += min( arr[i-1][1], arr[i-1][2] );
        arr[i][1] += min( arr[i-1][0], arr[i-1][2] );
        arr[i][2] += min( arr[i-1][0], arr[i-1][1] );
    }
    cout << min(min(arr[N-1][0], arr[N-1][1]), arr[N-1][2]);

    return 0;
}

 

이상으로 백준 1149번 자세한 설명과 함께 C++ 정답 코드였습니다.

감사합니다.