반응형
최댓값
-
알고리즘: 백준 11052번 카드 구매하기(feat.c++)알고리즘/백준(BaekJoon) 2020. 8. 23. 18:13
백준 11052번 링크입니다. 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 다이나믹 프로그래밍을 이용하면 쉽게 해결할 수 있다. 우선 코딩하기 전에 dp[n]을 말로 정의하는 게 중요하다. dp[n] = n개의 카드를 구매했을 때 최댓값 라고 하자 dp[n]을 구하기 위해서는 다음과 같은 과정을 거친다. (편의상 k번째 dp[n]을 dpk[n]라고 하자) dp1[n] = dp[n - 1] + packs[1] dp2[n] = dp[n - 2] + packs[2] dp3[n] = dp[n - 3] + packs[3] ..