1149번: RGB거리(백준 C++)

1149번: RGB거리 링크

코드

#include <iostream>
using namespace std;

// RGB 거리
int rgb[1000][3];

// 집을 색칠하는데 드는 비용 입력 받기
void init(int n){
    for(int i=0; i<n; i++){
        cin >> rgb[i][0] >> rgb[i][1] >> rgb[i][2];
    }
}

void solve(int n){
    for(int i=1; i<n; i++){
        for(int j=0; j<3; j++){
            if(rgb[i-1][(j+1) % 3] < rgb[i-1][(j+2) % 3]){
                rgb[i][j] += rgb[i-1][(j+1) % 3];
            }
            else{
                rgb[i][j] += rgb[i-1][(j+2) % 3];
            }
        }
    }
    int min = 1000001;
    for(int k=0; k<3; k++){
        if( rgb[n-1][k] < min ) min = rgb[n-1][k];
    }
    cout << min;
}
int main() {
    int n;
    cin >> n;
    init(n);
    solve(n);
    return 0;
}

풀이 및 사견

문제

선형으로 집이 N개 놓여져 있다고 생각하자.
각 집은 R, G, B 3개의 색 중 하나다. 단, 이전 집에 칠한 색으로는 할 수 없다.
색마다 칠하는 비용이 다르다고 하면, 칠하는데 드는 가장 최소의 비용은?

---

점화식

생각을 단순하게 해야한다.
N번째 집을 칠할때 최소의 비용이 되려면?

(N -1)번째 집까지 칠하는데 드는 최소의 비용 + N번째 집을칠하는 최소의 비용

단 R, G, B 선택에 따른 최소값이 각 각 다르므로 3가지 색에 대한 최소값을 모두 구해야 한다

• 전체 색에서의 최소값만 구하게 된다면 어떤 문제점이?

위의 경우를 보자

• N = 1 최소값

  1, 색상 R

• N = 2 최소값

  N = 1 까지의 최소값은 1이고, 색상은 R
  N = 2에서 색상이 R이 아닌 것 중 최소값 1, 색상 G
  N = 2까지의 최소값 1 + 1 = 2

• N = 3 최소값 :

  N = 2 까지의 최소값은 2이고, 색상은 G
  N = 3에서 색상이 G가 아닌 것 중 최소값, 888 색상 B
  N = 3까지의 최소값 2 + 888 = 890

뭔가 이상하다.

그림만 보고 곰곰히 생각해보면 최소비용은
R - > B - > G 순으로 칠해져서
1 + 5 + 1 이 되어야 하지만
N = 2 일때 그 순간의 최소값이 2라는 함정에 빠지게 된 것이다.

따라서 점화식은 R, G, B 에 따른 3개를 운용해야 한다.

변수

int rgb[1000][3];

집을 칠하는 데 필요한 비용을 담는 배열을 선언한다.
rgb[집의 개수][색의 개수]
이후, Input 따라 배열을 채워준다.

풀이

void solve(int n){
    for(int i=1; i<n; i++){
        for(int j=0; j<3; j++){
            if(rgb[i-1][(j+1) % 3] < rgb[i-1][(j+2) % 3]){
                rgb[i][j] += rgb[i-1][(j+1) % 3];
            }
            else{
                rgb[i][j] += rgb[i-1][(j+2) % 3];
            }
        }
    }
    int min = 1000001;
    for(int k=0; k<3; k++){
        if( rgb[n-1][k] < min ) min = rgb[n-1][k];
    }
    cout << min;
}

이중 반복문을 써서 각 N에 대한 각 색상별 최소값을 구하게 된다.
i는 N을 나타내는 변수
j는 색상을 나타내는 변수 0:R 1:G 2:B

j= 0이면 이전 N의 j = 1 과 j = 2를 비교해서 작은값과 더해줘야한다.
j = 1이면 이전 N의 j = 0 과 j = 2를 비교해서 작은값과 더해줘야한다.
j = 2이면 이전 N의 j = 0 과 j = 1를 비교해서 작은값과 더해줘야한다.

이는

if(rgb[i-1][(j+1) % 3] < rgb[i-1][(j+2) % 3]){
                rgb[i][j] += rgb[i-1][(j+1) % 3];
            }
            else{
                rgb[i][j] += rgb[i-1][(j+2) % 3];
            }

이렇게 할 수 있다.

이렇게 N = 3까지 진행하게 되면

N = 3 에서 RGB는 (96, 172, 185)

이 셋 중 최소값을 구하게 되면 96으로 96이 정답이 된다.