[백준] 1149번: RGB거리 - Python

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

1149번: RGB거리

아이디어

• case가 빨 초 파 3개뿐이니 3가지 경우의 처리만 해주면 될 듯
• dp테이블을 만들고 첫 시작은 li와 같게 설정하고
• dp[i][j] = min(dp[i-1][중복되지 않는 경우], dp[i-1][중복되지 않는 경우])+li[i][j] 이런 식의 점화식을 사용
• 2중 for문을 돌며 dp 테이블을 다 채우고 dp배열의 마지막 요소의 min() 값을 출력하면 될 듯

구현

import sys

input = sys.stdin.readline

n = int(input())

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

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

dp[0] = li[0]

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

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

마무리

• 오랜만에 풀어본 dp 아직 녹슬지 않은 듯?
• 그래프 탐색 백트래킹은 좀 감이 잡히니까 dp도 다시 풀어서 감을 찾아야겠다.
• 굿