백준|11052번|카드 구매하기

문제설명

들어있는 카드의 개수가 다른 카드팩들의 가격을 입력받고 원하는 개수의 카드를 살 수 있는 가장 비싼 가격을 출력하는 문제입니다.

​

작동 순서

1. 카드팩의 개수를 입력받습니다.(카드팩의 개수는 원하는 카드의 개수입니다.)

2. 카드팩의 가격을 입력받습니다.

3. 카드팩의 가격들을 비교하며 i장의 카드를 사는데 i장이 들어있는 카드팩을 사는것과 i-j장이 들어있는 카드팩과

j장짜리 카드팩을 사는 것이 더 비싼지 비교하고 비싼 값을 가져갑니다.

4. 원하는 개수의 카드를 사는데 필요한 값을 출력합니다.

​

소스코드

import sys
N = int(sys.stdin.readline())
price = [0]+list(map(int, sys.stdin.readline().split()))
for i in range(1, N+1):
for j in range(1, i//2+1):
price[i] = max(price[i], price[j]+price[i-j])
print(price[N], end="")