반응형
dynamic programming
-
백준 11052 - 카드 구매하기백준 algorithm 2020. 4. 14. 15:42
=> DP 문제입니다. => 카드 i개를 구매할 때의 최대 비용을 생각해야 합니다. => D[i] : 카드 i개 구매하는 최대 비용 =>카드 i개를 구매하는 방법의 가짓수 카드 1개 들어있는 카드팩 구매, 카드 i - 1개 구매 카드 2개 들어있는 카드팩 구매, 카드 i - 2개 구매 .... .... .... 카드 i 개 들어있는 카드팩 구매, 카드 0개 구매 이를 나타내면 P[1] + D[i-1] 위와 같이 표현할 수 있습니다. 이를 코드로 표현하면 for(int i=1; i N; vector P(N+1); vector D(N+1); int tmp; for(int i=1; i> tmp; P[i] = tmp; } for(int i=1; i