[BOJ] 17404번: RGB거리 2

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

17404번: RGB거리 2

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

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

 

입력

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

 

출력

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

 

---

풀이

📌 다이나믹 프로그래밍 (DP)

 

첫 번째 집을 빨강으로 칠하는 경우, 초록으로 칠하는 경우, 파랑으로 칠하는 경우 각각 생각해야 한다.

dp[i][j]에서 j가 0이면 i번째 집을 빨강으로, j가 1이면 초록으로, j가 2이면 파랑으로 칠한다 하자.

arr[i][j]는 i번째 집을 j번째 색으로 칠하는 비용이라 하자. (0=빨강, 1=초록, 2=파랑)

 

i번째 집은 (i-1)번째 집의 색을 제외한 색을 칠해야 한다.

i번째 집을 빨강으로 칠할 경우 (i-1) 번째 집을 칠하는 경우는 다음과 같다.

 

1) (i-1)번째 집을 초록으로 칠할 경우

dp[i][0] = dp[i-1][1] + arr[i][0]

 

2) (i-1) 번째 집을 파랑으로 칠할 경우

dp[i][0] = dp[i-1][2] + arr[i][0]

 

이 두 가지 경우 중 최소값을 선택해야 하므로 점화식은 다음과 같다.

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

 

첫 번째 집을 빨강으로 칠하는 경우 마지막 집은 파랑 또는 초록 중 최소값이 되는 경우로 칠해야 한다.

첫 번째 집을 빨강으로 칠하면 dp[1][0] = arr[1][0]이며 dp[1][1]과 dp[1][2] (빨강으로 칠하지 않는 경우)는 계산 편리를 위해 집 전체를 칠하는 비용의 최댓값인 1000000으로 한다. 

 

코드

#include <iostream>
using namespace std;

#define MAX 1000000

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n;
  int arr[1001][3]; //0 = red, 1 = green, 2 = blue
  
  cin >> n;

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

  int ans = MAX;
  for(int i = 0; i <= 2; i++) {
    
    int dp[1001][3];
    for(int k = 0; k <= 2; k++) {
      if(i == k) dp[1][k] = arr[1][k];
      else dp[1][k] = MAX;
    }

    for(int j = 2; j <= n; j++) {
      dp[j][0] = min(dp[j-1][1], dp[j-1][2]) + arr[j][0];
      dp[j][1] = min(dp[j-1][0], dp[j-1][2]) + arr[j][1];
      dp[j][2] = min(dp[j-1][0], dp[j-1][1]) + arr[j][2];
    }

    for(int k = 0; k <= 2; k++) {
      if(i == k) continue;
      else ans = min(ans, dp[n][k]);
    }
  }

  cout << ans;
  return 0;
}

 

결과