[백준] 9461번(python 파이썬)

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

 

현재 선택한 색에 따라 나뉘어 지는 경우의 수가 2가지씩 존재한다. 마찬가지로 다음 상태는 이전상태에서 올 수 있는 경우의 수가 2가지 존재한다.

 

때문에 다음 상태는 이전 상태(2가지)중 작은 값을 찾아서 더해주면 된다.

 

-> 2차원 배열로  dp를 만들어준다.

 

참고 자료 https://m.blog.naver.com/occidere/220785383050

첫번째 행은 첫번째 집들의 비용을 넣으면 된다.

 

import copy

n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]
dp = [[10001] * 3 for _ in range(n)]
def RGB():
    for i in range(n):
        for j in range(3):
            if i == 0:
                dp[i][j] = cost[i][j]
            else:
                if j == 0:
                    dp[i][j] = min(dp[i-1][1], dp[i-1][2]) + cost[i][j]
                elif j == 1:
                    dp[i][j] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][j]
                else:
                    dp[i][j] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][j]
RGB()
print(min(dp[n-1]))

 

 

사실 계속 트리를 그리면서 생각해서 dp 점화식이 떠오르지 않았다.. 

점화식을 떠올릴때 큰 값을 어떻게 작은값을 이용해서 만드는지 부터 생각하자

 

답보니까 너무 쉬운 문제였다.