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

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

11052번: 카드 구매하기

 

 

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

 

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

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

 

아래 코드는 top - down 방식으로 작성한 코드이다.

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

def get_max_price(n):
  if max_price[n]:
    return max_price[n]
  else:
    max_price[n] = price[n]
    for i in range(1, n):
      t = get_max_price(i) + price[n-i]
      if t > max_price[n]:
        max_price[n] = t
    return max_price[n]

print(get_max_price(N))