[동적 계획법] RGB 거리
2021. 10. 24. 12:57ㆍ백준
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
이번 문제를 풀면서 DP 테이블 개념을 알게 되어서 좋았다.
재귀 & 메모이제이션이 아니라 이런 식으로도 풀 수 있구나 하는...
역시 아직 배울게 많다 ㅠ
from sys import stdin
N = int(stdin.readline())
L = []
RESULT = []
while True:
[R, G, B] = map(int, stdin.readline().split())
if len(L) == 0:
L.append([R, G, B])
else:
prev = len(L) - 1
L.append([
R + min([L[prev][1], L[prev][2]]),
G + min([L[prev][0], L[prev][2]]),
B + min([L[prev][0], L[prev][1]]),
])
if len(L) == N:
break
print(min(L[len(L) - 1]))