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

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

16194번: 카드 구매하기 2

 

 

• 부분 반복 구조 : min_price[n] = min_price[0] + price[n] 또는 ... min_price[n-1] + price[1]
• 최적 부분 구조 : min_price에는 항상 가능한 최소의 값이 저장된다. 
• 메모이제이션 : n+1 크기의 배열 min_price 생성
• 접근 방식 : bottom - up 방식 ( 이유 : min_price[1]을 알기 때문)

N = int(input())
price = [0] + list(map(int, input().split()))
min_price = [0] * (N+1)

for i in range(1, N+1):
  min_price[i] = price[i]
  for j in range(i):
    t = min_price[j] + price[i-j]
    if t < min_price[i]:
      min_price[i] = t
print(min_price[N])

 

아래 코드는 top - down 방식의 코드이다.

N = int(input())
price = [0] + list(map(int, input().split()))
min_price = [0] * (N+1)

def get_min_price(n):
  if min_price[n]:
    return min_price[n]
  else:
    min_price[n] = price[n]
    for i in range(1, n):
      t = get_min_price(i) + price[n-i]
      if t < min_price[n]:
        min_price[n] = t
    return min_price[n]

print(get_min_price(N))