[Python]동적계획법 백준 1149

   문제

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

이전문제들보다는 조금 복잡한 형태가 될거같다.

이웃과 같은색으로 칠할수 있다면 이전 최솟값에 집을 칠하는 비용의 최솟값을 더하면 간

단히 구해질수 있지만 조건이 이웃과 같은 색을 칠할수 없다는 것에서 문제가 조금 복잡해 

질거같다.코드로 구현하는게 어려웠다.

import sys
# 집의 수
n = int(sys.stdin.readline())
rgb_pay = [[0] * 3 for i in range(n)]
 
for i in range(n):
    # 각 색별 페인트 비용
    rgb_pay[i][0], rgb_pay[i][1], rgb_pay[i][2] = map(int, sys.stdin.readline().split())
 
#이번에 빨강,초록,파랑을 골랐을때의 최솟값이 들어간다.0=빨강 1=초록 2=파랑
rgb_sum = [[0] * 3 for i in range(n)]
 
for i in range(n):
    if i == 0:
        rgb_sum[i] = rgb_pay[i]
 
    else:
        # 이번에 빨강을 고를때 최솟값(파랑,초록 둘중 작은거)
# 이번에 초록을 고를때 이전값들중에서 최솟값(빨강,파랑)
# 이번에 파랑을 고를때 이전값들중에서 최솟값(빨강,초록)
        rgb_sum[i][0] = rgb_pay[i][0] + min(rgb_sum[i - 1][1], rgb_sum[i - 1][2])
        rgb_sum[i][1] = rgb_pay[i][1] + min(rgb_sum[i - 1][0], rgb_sum[i - 1][2])
        rgb_sum[i][2] = rgb_pay[i][2] + min(rgb_sum[i - 1][0], rgb_sum[i - 1][1])
 
 
print(min(rgb_sum[n - 1]))    #최종적으로 빨강,파랑,초록 을 골랐을때 최솟값