백준 - 1149번(DP)

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

1149번: RGB거리

pypy3

import sys

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

arr = []

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

for i in range(1,len(arr)):
    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][1], arr[i-1][0]) + arr[i][2]

print(min(arr[-1]))

DP문제라고? 최소비용을 구하고 싶다고? 그럼 min함수 쓰는 문제임.
만들 수 있는 작은 값으로 계속 만들어나가면 된다. 0번에 집 지으면 1,2, 번만 집을 지을 수 있다.
이전에 나올 수 있는 조합중에 작은 것만 신경 쓰면서 가면 된다.
쉽게 생각하면 첫번째첫 번째 뭘 고르는지가 중요한데 그걸 알 수 없으니깐 첫 번째 출발지점에 있는 애들로부터 전부 출발해서 전부 최솟값을 만들어 보자!
이게 이 문제의 취지다. 그중에서 최소값이 위 문제의 조건으로 만들 수 있는 최솟값이기 때문이다.