C++ - 백준 1149번. RGB거리

 

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.

- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

-i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

 

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

3 26 40 83  49 60 57 13 89 99

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

예제 (답: 96)

 

해결 방법

우선 해결하기 위해서 Dynamic Programming을 사용했다.

아래의 그림을 보면 같은 연산이 반복되기 때문에 memoization을 통해 각 단계에서 필요한 비용의 최솟값을 저장한다.

for문을 돌아 첫번째 집에 도착하게 되면, 최종적으로 모든 집을 색칠하는 비용의 최솟값을 얻을 수 있다.

 

예제 푸는 방법

#include <iostream>
using namespace std;

//RGB거리 - DP
int min(int x, int y) {
  return x<y ? x:y;
}
int main() {
  int n;
  cin >> n;
  int House[n][3];
  int min_val = 1000000;

  for(int i=0 ; i<n ; i++) {
    cin >> House[i][0] >> House[i][1] >> House[i][2]; // R
  }
  for(int i=n-2 ; i>=0 ; i--) {
    // 일단 맨 마지막 집은 각자 자기의 R,G,B값 가지기
    // --> i가 n-2부터 시작하면 해결완료
    for(int j=0 ; j<3 ; j++) {
      // 마지막집이 아니면, 자기와 똑같지 않은 색깔들중에서 min값과 자신의 값을 더한 값을 가진다.
      // R인 경우 : 0번 인덱스
      if(j == 0)  House[i][0] += min(House[i+1][1], House[i+1][2]);
      // G인 경우 : 1번 인덱스
      if(j == 1)  House[i][1] += min(House[i+1][0], House[i+1][2]);
      // B인 경우 : 2번 인덱스
      if(j == 2)  House[i][2] += min(House[i+1][0], House[i+1][1]);
      if(i==0) {
        if(House[i][j] < min_val) {
          min_val = House[i][j];
        }
      }
    }
  }
  cout << min_val;

}