[백준-1149] RGB 거리

문제

링크

코드

n = int(input())

house = []

for _ in range(n) :
    house.append(list(map(int, input().split())))


for i in range(1, n) :
    house[i][0] = min(house[i-1][1], house[i-1][2]) + house[i][0]
    house[i][1] = min(house[i-1][0], house[i-1][2]) + house[i][1]
    house[i][2] = min(house[i-1][0], house[i-1][1]) + house[i][2]

print(min(house[n-1][0], house[n-1][1], house[n-1][2]))

풀이

규칙

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

문제의 규칙을 한 문장으로 정리하면 다음과 같다.

인접한 집끼리 색이 같지 않아야 한다.

DP는 점화식을 먼저 구해야 하므로 점화식을 구해보도록 하자.
i번 집을 칠했을 때 최솟값을 구해야 한다.
2번 집을 칠했을 때 = 1번 집 + 2번 집
3번 집을 칠했을 때 = 2번 집(1번 집 + 2번 집) + 3번 집 이므로

• 점화식 : i번 집까지 칠한 가격 = (i-1번 집 칠한 최소 가격) + i번 집 칠한 가격
  -> house[i][0] = min(house[i-1][1], house[i-1][2]) + house[i][0]

그리고 마지막 집에서 R, G, B 각각 칠한 가격의 최솟값이 바로 모든 집을 칠하는 최솟값이다.