[백준] 11052 : 카드 구매하기

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

---

• 우선 처음에는 카드뭉치별로 각각의 갯수당비용을 구해서 그리디한 방식으로 구하려고 했으나, 대충 안된다는 걸 깨달음.
• N개 카드의 갯수를 확실히 맞춰야 한다는 것에 포커스를 둔다면 카드를 뽑을 수 있는 조합은 N 개가 된다.
• 0 + N, 1 + N-1 , 2 + N-2, ... N-1 + 1
• 이 경우 왼쪽의 0, 1, ... , N-1 개의 카드를 뽑을때의 최댓값을 알고 있다면, 오른쪽의 나머지 카드 갯수는 입력받은 값으로 구할 수 있다.
• i 개의 카드를 뽑을 때의 최댓값들이 결국 i 개 이후에도 쭉 사용되기 때문에, 이를 재사용하면서 다 구하면 풀 수 있다.
• 파이썬이 확실히 간결해 보이게 코드 짜기가 쉬운 것 같다.

---

N = int(input())
cards = [0] + list(map(int, input().split()))   # 입력받는 각 카드팩의 비용
scores = [0] * 1001                             # i개의 카드를 구매할때의 최댓값
for i in range(1,N+1):                          # scores 리스트를 채워나감. (1개~N개 최댓값들)
    scores[i] = max(scores[idx] + cards[i-idx] for idx in range(i)) 
    # 각 최댓값은, (idx개 카드 최댓값 + 남은 카드갯수뭉치의 비용) 들 중 최댓값이 됨.
print(scores[N])