백준 11052

[baekjoon 11052] 카드 구매하기- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 이 문제는 비교적 빠르게 풀었다. 며칠 동안 dp만 잡고 있었더니 좀 익숙해지는 것 같기도 하고.. 우선 카드의 개수는 그 숫자가 가지고 있는 인덱스이다. 10,15,20,30 -> 카드 한 장 사는데 10원, 카드 두 장 사는데 15원, 세 장은 20원, 네 장은 30원 따라서 처음 접근할 때는 결국 자연수들의 합으로 N을 만드는 경우의 수들을 구한 뒤에, 그 경우의 수를 인덱스 삼아서 max값을 찾으면 되겠다.라고..