[백준] 11052 카드 구매하기

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

필요한 카드의 개수가 1개부터 최고의 금액을 구하며, N개일때까지 구하였습니다.

2) 알고리즘

• 다이나믹 프로그래밍

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())                           # 필요한 카드의 개수
price = list(map(int, sys.stdin.readline().split()))    # 입력으로 주어지는 카드팩별 금액

dp = [0] * (N+1)                        # 카드의 개수별 최고 금액

for i in range(1, N+1):                 # 카드 N개까지 인덱스 반복
    cases = {price[i-1]}                # 카드 i개가 들어있는 팩을 하나 샀을 경우
    for j in range(1, i):               # 이전에 구한 카드 최대 개수들 조합
        cases.add(dp[j] + dp[i-j])      # ex. 5개 => 1 + 4, 2 + 3
    
    dp[i] = max(cases)                  # 최대 비용을 dp에 저장

print(dp[N])

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

11052번: 카드 구매하기

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다