[백준-11052] 카드 구매하기 / Python
📚 Problem Solving/Baekjoon
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
import sys
input = sys.stdin.readline
n = int(input())
card = list(map(int, input().split()))
d = [0] * (n + 1)
d[1], d[2] = card[0], max(card[0] * 2, card[1])
for i in range(3, n + 1):
d[i] = card[i - 1]
for j in range(1, i // 2 + 1):
d[i] = max(d[i], d[j] + d[i - j])
print(d[n])
해설
나에게는 난이도가 있었던 dp문제였다..
예를 들어, d[3]을 구하는 경우에는 3장 팩 하나, 1장 팩 하나+d[2] 중 최댓값이다. 여기서 1장 팩 3개를 이용하는 경우와, 1장 팩 하나 + 2장 팩 하나를 이용하는 경우는 d[2]에서 처리가 끝난 것이다.
d[n]을 구하는 방법은 n장 팩 1개, 1과 d[n-1], d[2]와 d[n-2], ..d[i]와 d[n-i]를 만드는 것 중 중 최대인 수이다.
'📚 Problem Solving > Baekjoon' 카테고리의 다른 글
[백준-14503] 로봇 청소기 / Python (0) | 2021.06.19 |
---|---|
[백준-2960] 에라토스테네스의 체 / Python (0) | 2021.06.18 |
[백준-18353] 병사 배치하기 / Python (0) | 2021.06.04 |
[백준-2407] 조합 / Python (0) | 2021.06.01 |
[백준-1629] 곱셈 / Python (0) | 2021.06.01 |