1149_RGB거리 (C++)

1149번: RGB거리

#include <iostream>
#include <cstring> //memset
#include <algorithm> //min
using namespace std;

int n;
int house[1001][3] = {0,};
int cal[1001][3] = {0,};

int main(){
    cin >> n;

    for(int i=0; i<n; i++){
        for(int j=0; j<3; j++){
            cin >> house[i][j];

            if(i==n-1){
                cal[i][j] = house[i][j];
            }
        }
    }

    for(int i=n-2; i>=0; i--){
        cal[i][0] = min(cal[i+1][1],cal[i+1][2]) + house[i][0];
        cal[i][1] = min(cal[i+1][0],cal[i+1][2]) + house[i][1];
        cal[i][2] = min(cal[i+1][0],cal[i+1][1]) + house[i][2];
    }

    cout << min({cal[0][0],cal[0][1],cal[0][2]});

    return 0;
}

 

RGB를 선택하는 모든 경우를 탐색하는 방식은 당연히! 시간초과가 난다.

 

 

나는 입력받은 배열의 가장 마지막 행을 기준으로 0행까지 올라가며 비용의 최솟값을 구했다.

 

 

예시)

 

2 1 3

2 1 5

5 4 3  를 입력받았을 때, 내가 푼 방식으로 비용의 최솟값을 구해보자.

 

비용을 계산하는 과정을 수행하기 전에, 가장 먼저 해주어야할 것은 시작점을 만들어야 한다.

우리는 가장 마지막 행(n-1번째 행)에서부터 올라갈 것이므로, 마지막 행이 시작점(기준)이 된다.

 

 

n-2번째 행 ~ 0번째 행까지 계산 과정은 다음과 같다.

X행의 세 가지 숫자는 X+1행의 숫자를 기준으로 변경된다.

X행0열 은 X행0열의 비용 +  X+1행1열과 2열의 최솟값,

X행1열 은 X행1열의 비용 +  X+1행0열과 2열의 최솟값,

X행2열 은 X행2열의 비용 +  X+1행0열과 1열의 최솟값 으로 계산할 수 있다.

 

 

 

위의 과정을 n-2번째 행 ~ 0행까지 수행하면,

0행0열의 숫자는 : 첫 번째 숫자를 R색상으로 선택했을 때의 총 최소 비용,

0행1열의 숫자는 : 첫 번째 숫자를 G색상으로 선택했을 때의 총 최소 비용,

0행2열의 숫자는 : 첫 번째 숫자를 B색상으로 선택했을 때의 총 최소 비용 을 의미한다.

 

그러므로, 모든 경우 중에서의 최소 비용은 0행0열,0행1열,0행2열 중 최솟값이 된다.