11052
[BOJ] 11052 카드 구매하기 (Python / 파이썬)
[BOJ] 11052 카드 구매하기 (Python / 파이썬)
2021.08.01🧷 문제 https://www.acmicpc.net/problem/11052 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하는 문제이다. 🛠 풀이 이 문제는 Bottom-Up 방식의 다이나믹 프로그래밍(DP)를 이용하여 해결할 수 있다. Step 1. 이 문제를 풀기 위해 생각을 해보면 n개의 카드를 구매하기 위한 최대 금액 d[n]은 d[n], d[1] + d[n-1], d[2] + d[n-2], ... , d[j] + d[n-j]중 가장 큰 값과 같다. Step 2. for문을 돌기 전 d[i]의 값을 입력으로 받은 card_pack[i]로 초기화 시켜준 후에 j == 1와 j == i-1은 같으므로 j는 i의 절반까지만 돌도록 한다. Step 3. f..