[백준] 1149번 | RGB 거리

6166 단어 AlgorithmsAlgorithms

풀기 전 생각

dp 문제로 접근하면 되겠다.
매번 자신과 다른 색의 합들을 더해주면서 진행하면 되겠다.

코드

import sys

n = int(sys.stdin.readline())
arr = list()

for i in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))

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

print(min(arr[n-1][:]))

리뷰

dp 파트가 알고리즘 중에 제일 취약한 부분인 것은 알고 있었지만, 이런 기본 문제도 빠르게 해결하지 못해 아쉬웠던 문제. 차근차근 해결해 나가자.

좋은 웹페이지 즐겨찾기