백준 1149번_RGB거리 (Python)

문제

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

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

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

 

코드

N = int(input())
cost = []
dp = [[None]*3 for i in range(N)]
for i in range(N):
    cost.append(list(map(int, input().split())))
dp[0] = cost[0]
for i in range(1, N):
    dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])
    dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2])
    dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1])
print(min(dp[N-1]))

 

풀이

우선 문제의 규칙을 해독하면, 서로 이웃한 집에는 같은 색이 칠해지면 안된다. (약간 4색 정리랑 비슷한 느낌이랄까?)

보통 조건이면 경우의 수를 구하는 문제였겠지만 이 문제는 각 색을 칠할 때마다 집별로 차등한 가중치(비용)이 발생해서 최솟값을 구하는 문제로 바뀌었다...

이때까지의 집들의 색깔 배열에 바로 다음 집 색깔이 긴밀히 영향을 받으므로 이들의 색을 차근차근 구해가는 문제로 바꾸어 DP(동적 계획법)을 쓰는 것이 현명할 것이다.

 

일단 첫번째 집은 빨강, 초록, 파랑(R, G, B로 축약해 부르겠다) 셋 중 어느 것이든 상관이 없다.

그다음 집을 생각해보면 경우는 다음과 같이 존재한다.

• 두번째가 R: 첫번째는 B또는 G
• 두번째가 B: 첫번째는 R 또는 G
• 두번째가 G: 첫번째는 R 또는 B

두번째 집의 색깔에 대한 각 경우에 대해서 (두번째집 색칠 비용) + (첫번째집 색칠 비용 선택지 둘 중 최솟값)을 각각 저장한다.

그다음 세번째 집의 색깔도 똑같이 경우를 나눌 수 있다.

• 세번째가 R: 두번째는 B또는 G
• 세번째가 B: 두번째는 R 또는 G
• 세번째가 G: 두번째는 R 또는 B

여기에서 예를 들어 세번째가 R인 경우, 비용을 계산할 때 두번째가 B인 경우 혹은 G인 경우는 각각 경우의 비용 최솟값을 채용하면 된다. 즉, 아까 저장해놓았던 값을 그대로 사용하면 된다. 그리고 세번째 집까지의 비용의 최솟값 각각에 대해서 다시 저장을 해두면 된다.

네번째, 다섯번째... 그 다음 경우들 모두 동일하다. 이를 위해서 코드에서 3*n의 리스트를 만든 것이다. 이렇게 저장해가는 과정을 계속 반복해가면 시간복잡도 O(n) 안에 문제를 끝낼 수 있다.