RGB거리

백준 1149

방법1. 동적 계획법

---

import sys

n = int(sys.stdin.readline())
home = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

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

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

처음에 위의 조건들을 보고 어떻게 문제를 풀어야하나 고민이 많았다. 동적 계획법을 쓰는 방식인 것 같긴 한데 어떤식으로 해야하는 거지 싶었다. 첫 번째 집에서 어떤걸 선택하고 -> 두 번째 집에서 어떤걸 선택하고.. 이런식으로 생각했었는데, 첫 번째 행은 그대로 넣어두고 두 번째 행의 R자리에(R을 칠한다고 하면)는 첫 번째 행에서 G와 B중 최솟값과 R가격을 더해서 넣고~ 이런 식으로 하는 거였다.
코드는 엄청 간단하다!