[백준] 1149번 문제 (RGB거리) 파이썬(Python) 풀이

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

1149번: RGB거리

import sys
input = sys.stdin.readline

n = int(input())
rgb = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * 3 for _ in range(n)]
dp[0][0] = rgb[0][0]
dp[0][1] = rgb[0][1]
dp[0][2] = rgb[0][2]

for i in range(1, n):
    for j in range(3):
        if j == 0:
            dp[i][j] = min(rgb[i][j] + dp[i - 1][j + 1], rgb[i][j] + dp[i - 1][j + 2])
        elif j == 1:
            dp[i][j] = min(rgb[i][j] + dp[i - 1][j - 1], rgb[i][j] + dp[i - 1][j + 1])
        else:
            dp[i][j] = min(rgb[i][j] + dp[i - 1][j - 2], rgb[i][j] + dp[i - 1][j - 1])

print(min(dp[n - 1]))

전형적인 DP 문제다.

 

j가 0이면 빨강,

j가 1이면 초록,

j가 2이면 파랑이다. 

 

규칙이 복잡하게 써 있지만 쉽게 말하면, 본인 집의 색을 제외한 다른 색을 선택하면 되는 것이다.

예를 들어 1번 집이 빨간색이면 2번 집은 초록 또는 파란색이면 된다.

 

따라서 dp 배열에 해당 규칙을 적용하여 최소값을 계속해서 누적시키고,

결과적으로 dp[n - 1]의 최소값을 출력하면 된다.