백준 문제 중 1149번, DP, ‘RGB거리’

풀이

백준 문제 중 1149번

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

문제

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

출력

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

---

문제의 핵심은 모든 경우의 수를 다 검토해야 한다는 것이다. 각각의 선택에서 최소 였다고 해도 마지막 총합이 최소가 아닐 겅우가 있기 때문이다.

n번집까지 칠하는 비용의 배열을 dp라 하자. dp는 nx3의 배열로 1~n번째 집까지가 각각 R, G, B로 칠한 경우의 최소비용을 각각 dp[n][0], dp[n][1], dp[n][2]에 저장한다.

dp[n]의 각 최소 비용을 구하는 방법은 dp[n-1]에서 R을 칠한 경우 dp[n]에서는 G와 B만을 칠할 수 있고, G를 칠한 경우 dp[n]에서 R과 B만 칠할 수 있고, dp[n-1]에서 B를 칠한 경우 dp[n]에서 R과 G만 칠할 수 있다. 각각의 경우에 대해서 최소 비용일때응 dp[n]에 저장하면 된다.

이를 수도코드로 대략 나타내면

dp[n]을 R로 칠하는 경우에 대해서는

dp[n][0] = min(rgb[n][0]+dp[n-1][1],rgb[n][0]+dp[n-1][2])이고

dp[n]을 G로 칠하는 경우에 대해서는

dp[n][1] = min(rgb[n][1]+dp[n-1][0],rgb[n][1]+dp[n-1][2])이고

dp[n]을 B로 칠하는 경우에 대해서는

dp[n][2] = min(rgb[n][2]+dp[n-1][1],rgb[n][2]+dp[n-1][0])이고

이다.

이를 코드로 나타내면 아래와 같다.

n = int(input())

rgb = [[]for _ in range(n)]

for i in range(n):

    rgb[i] = list(map(int,input().split()))

 # n x 3 의 dp 선언 후 0으로 초기화
dp = [[0,0,0]for _ in range(n)]

 # dp[0]와 rgb[0]을 같다.
dp[0] = rgb[0]

 # 비용을 구하는 경우의수
for i in range(1,n):
    dp[i][0] = min(rgb[i][0]+dp[i-1][1],rgb[i][0]+dp[i-1][2])
    dp[i][1] = min(rgb[i][1]+dp[i-1][0],rgb[i][1]+dp[i-1][2])
    dp[i][2] = min(rgb[i][2]+dp[i-1][0],rgb[i][2]+dp[i-1][1])

print(min(dp[-1]))

3
1 100 100
100 1 100
100 100 1
[[1, 100, 100], [200, 2, 101], [102, 201, 3]]
3

배운점

큰 문제를 작은 문제로 푸는 dp의 개념 중엔 가능한 최선의 방법들을 모두 나열하는 1149번도 해당됨을 배웠다.