카드 구매하기

[11052] 카드 구매하기

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 🔎 해결 방법 예를 들어 민규가 구매하고자 하는 카드의 개수가 4개라면, 가능한 조합은 4 / 3 + 1 / 2 + 2 / 2 + 1 + 1 / 1 + 1 + 1 + 1 이므로 자연수의 분할로 접근하면 되는 줄 알았다. 그러면 각 경우는 위와 같이 계산하면 되는데 2 +2 가 문제였다. dp를 생각하지 못하고 2 + 2를 계속 p[2] + p[2]라고 계산하는 바람에 점화식을 세울 수 없었다. 하지만! ..