Suhwanc

백준 16194번 카드 구매하기 2

문제 링크 : https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 DP(Dynamic programming) 문제입니다! bottom - up 방식으로 이 문제를 해결해보자면, 각 카드팩의 값을 p[1~n] 이라고 두면 카드 1개를 갖기 위한 금액의 최솟값(=d[1])은 p[1] 카드 2개를 갖기 위한 금액의 최솟값은 min(p[2],d[1]+p[1]) 카드 3개를 갖기 위한 금액의 최솟값은 min(p[3],d[2]+p[1],d[1]+p[2]) ..