[BOJ 1149] RGB 거리(Python)

문제링크

RGB 거리

풀이 전 계획 및 생각

가능한 모든 경우를 해보는데, 이전에 계산해놨던 것을 이용하는 메모이제이션을 이용해서 풀면 쉬운 문제였다.
min_price라는 배열을 만들고 각 인덱스별로 색깔을 정했다.
min_price[i][0] - 이번 집을 빨간색으로 칠할 경우 최소 비용을 저장
min_price[i][1] - 이번 집을 초록색으로 칠할 경우 최소 비용을 저장
min_price[i][2] - 이번 집을 파란색으로 칠할 경우 최소 비용을 저장
이렇게 설정을하고 아래와 같이 구현했다.

min_price[i][0] += r + min(min_price[i - 1][1], min_price[i - 1][2])
min_price[i][1] += g + min(min_price[i - 1][0], min_price[i - 1][2])
min_price[i][2] += b + min(min_price[i - 1][0], min_price[i - 1][1])

이렇게하면 이전 단계의 집과는 다른 색을 칠할 수 있고, 그 다음 단계에서 같은 연산을 반복하면 이번 단계의 집과 다른 색을 칠할 수 있다. 이 공식은 간단하게 N번 집의 색은 N-1번 집의 색과 같지않아야한다는 조건에서 유추했고, 유추한 후에 i-1,i,i+1번 집의 색이 같지 않은지 검증했다. 각 단계에서 이번에 칠하고 싶은 색을 칠했을 때, 최소 비용을 구하는 과정에서 이전 단계에서 이번 단계와 같은 색깔로 칠한 경우는 배제하고 생각하고, i-1,i+1번집의 색깔은 다를 필요가 없기때문에 문제가 없다는 결론을 내렸다.

풀이

import sys
min_price = [[0]*3 for _ in range(1001)]
n = int(sys.stdin.readline())
min_price[0][0],min_price[0][1],min_price[0][2] = map(int,sys.stdin.readline().split())
for i in range(1,n):
    r,g,b = map(int,sys.stdin.readline().split())
    min_price[i][0] += r + min(min_price[i - 1][1], min_price[i - 1][2])
    min_price[i][1] += g + min(min_price[i - 1][0], min_price[i - 1][2])
    min_price[i][2] += b + min(min_price[i - 1][0], min_price[i - 1][1])

temp = min_price[n-1]
print(min(temp))

풀이하면서 막혔던 점과 고민했던 점

주어진 조건에 맞는 점화식만 구하면 되는 문제였어서 크게 어려움은 없었다.

풀이 후 알게된 개념과 소감

DP문제는 풀기 전까지는 머리 아픈데, 푸는 순간 짜릿해서 재밌는 것 같다.