[백준 / #1149] RGB거리 (Python)

문제 설명

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

1149번: RGB거리

 

 

---

문제풀이

쉬운 DP 문제!?

연속해서 같은 색을 사용하면 안 된다는 조건만 잘 생각하면 쉽게 풀 수 있다.?

점화식은 ?dp[i]를 빨간색으로 칠하려면 DP[i-1]를 초록색으로 칠한 것과 파란색으로 칠한 것 중 더 적은 값 + 현재 칸을 빨간색으로 칠하는 값!

이렇게 현재 칸을 각각의 색깔로 칠할 수 있는 값을 다 구한 뒤 최솟값을 출력하면 된다.

N = int(input())
rgb = []

for _ in range(N):
    rgb.append(list(map(int, input().split())))

dp = list([0, 0, 0] for _ in range(1001))

dp[1][0] = rgb[0][0]
dp[1][1] = rgb[0][1]
dp[1][2] = rgb[0][2]

for i in range(2, N + 1):
    dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + rgb[i - 1][0]
    dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + rgb[i - 1][1]
    dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + rgb[i - 1][2]

print(min(dp[N]))