[BOJ] 1149번: RGB거리

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

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보다 작거나 같은 자연수이다.

 

출력

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

 

---

풀이

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

 

하나의 큰 문제를 여러 개의 작은 문제로 나누어서 접근하는 알고리즘이다.

결과 값들을 저장하여 다음 문제를 해결하는 데 사용한다.

 

i번째 집을 빨간색으로 칠했을 경우 house[i][0], 초록색일 경우 house[i][1], 파란색일 경우 house[i][2] 라하면 i번째 집의 색을 빨간색으로 칠하는 최소 비용은

min((i-1)번째 집을 초록색으로 칠하는 최소 비용, (i-1) 번째 집을 파란색으로 칠하는 최소 비용) + i번째 집을 빨간색으로 칠하는 비용이다. 초록색과 파란색도 이와 마찬가지로 계산한다.

 

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
  int n, r, g, b;
  int house[1001][3];
  cin >> n;

  house[0][0] = 0;
  house[0][1] = 0;
  house[0][2] = 0;
  for(int i = 1; i <= n; i++) {
    cin >> r >> g >> b;
    house[i][0] = min(house[i-1][1], house[i-1][2])+r;
    house[i][1] = min(house[i-1][0], house[i-1][2])+g;
    house[i][2] = min(house[i-1][0], house[i-1][1])+b;
  }

  cout << min(house[n][0], min(house[n][1], house[n][2]));  
}

처음에 DFS 문제인 줄 알고 DFS로 풀었으나 실행시간이 오래 걸려서 이 방법은 아닌 것을 알았다.

DP를 오랜만에 하다 보니 문제를 봤을 때 DP 문제인지 파악하기가 어려웠다. 

 

결과