[백준] 1149번: RGB거리 파이썬

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

1149번: RGB거리

다이나믹 하게 가보자

DP(Dynamic Programing)를 풀기 위해서는 먼저 테이블을 정의해야 하고 점화식을 찾은 후에 초기 값을 정해야 한다.

일단 점화식만 찾고나면 그 뒤는 초기 값을 채워넣은 후에 반복문을 돌면서 배열을 채우면 끝..

 

그치만 그 과정에서 능지가 좀 필요한 거같다..

 

난.

능지부족; 해서 걍 여러개 풀면서 감 잡으려한다..

 

풀이

 

일단 초기 값을 정하는게 중요

D[i][0] = i+1번째 까지 칠하는 최소비용, 단 i+1번째 집은 빨간색

D[i][1] = i+1번째 까지 칠하는 최소비용, 단 i+1번째 집은 초록색

D[i][2] = i+1번째 까지 칠하는 최소비용, 단 i+1번째 집은 파랑색

 

점화식은 

D[i][0] = min(D[i-1][1]+cost[i][0], D[i-1][2]+cost[i][0])

i+1번째 까지 칠하는 최소비용(i+1번째 집 빨간색)은

i번째 집까지 칠하는 최소 비용(i번쨰 초록집) + i+1번째 집 빨갛게 칠하는비용 ,   i번째 집까지 칠하는 최소 비용(i번쨰 파랑집) + i+1번째 집 빨갛게 칠하는비용 

이거 두개 중 더 작은 비용인 것이다...

 

이거만 생각해내면 구현은 간단하다.!

import sys
n = int(sys.stdin.readline())
cost = [[]] * n
D = [[0 for _ in range(3)]for _ in range(n)]

for i in range(n):
  cost[i] = list(map(int, sys.stdin.readline().split()))

D[0][0] = cost[0][0]
D[0][1] = cost[0][1]
D[0][2] = cost[0][2]

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