-
알고리즘: 백준 11052번 카드 구매하기(feat.c++)알고리즘/백준(BaekJoon) 2020. 8. 23. 18:13
백준 11052번 링크입니다.
다이나믹 프로그래밍을 이용하면 쉽게 해결할 수 있다.
우선 코딩하기 전에 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]
...
dpn[n] = dp[n - (n - 1)] + packs[n - 1]
∴ dp[n] = max(dp1[n], dp2[n], dp3[n], ... dpn[n])
코드로 표현하면 다음과 같다.
for(int i = 1; i <= n; i++) dp[n] = max(dp[n], dp[n - i] + packs[i]);
dp[1] 부터 차례로 값을 넣어가야 하므로 이중for문을 이용한다.
#include<iostream> using namespace std; int max(int x, int y) { if (x > y) return x; return y; } int main() { int packs[1001] = {0}; int dp[10001] = {0}; int N; scanf("%d", &N); for (int i = 1; i <= N; i++)scanf("%d", &packs[i]); for (int i = 1; i <= N; i++) for (int j = 1; j <= i; j++) dp[i] = max(dp[i], dp[i - j] + packs[j]); printf("%d", dp[N]); return 0; }
반응형'알고리즘 > 백준(BaekJoon)' 카테고리의 다른 글
알고리즘: 백준 14888번 연산자 끼워넣기(feat. python) (0) 2020.08.24 알고리즘: 백준 11057번 오르막 수 (feat. c++) (0) 2020.08.24 알고리즘: 백준 1697번 숨바꼭질 (feat. c++) (0) 2020.08.23 알고리즘: 백준 2667번 단지번호붙이기 (feat. c++) (0) 2020.08.22 알고리즘: 백준 1010번 다리놓기 (feat. c++) (0) 2020.08.18