https://www.acmicpc.net/problem/11052
1.dp 관찰방법
i행에 주머니(동전)을 한개씩 !추가! 하면서 target(N개 카드) 를 채워나간다.
2.의사코드
1. i행에 1번째 주머니, 2번째 주머니를 추가해나가면서 관찰한다.
2. 관찰결과 위쪽(이번에 추가된 주머니 미사용하는경우) 과
d[j-i] + arr[i]( j-i개 카드를 추가하기 위해 이번에 추가된 주머니 사용하는경우)를 비교해야함을 알아낸다.
3.전체코드
#include <bits/stdc++.h>
using namespace std;
int n,a[1004],dp[1004][1004];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
//dp[i][j] : i번째 주머니 !!추가!!시, j개카드를 만드는데 드는 최대비용
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (j - i >= 0) {
dp[i][j] = max(dp[i - 1][j], dp[i][j-i]+a[i]);
}
else
dp[i][j] = dp[i - 1][j];
}
}
/*for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
cout << dp[i][j]<<" ";
}
cout << "\n";
}*/
cout << dp[n][n];
return 0;
}
'Algorithm > dp' 카테고리의 다른 글
백준 2240 자두나무 c++ // 탑다운디피, 재귀디피 형식, 비트연산자, memset사용법 (0) | 2024.04.26 |
---|---|
백준 1699 제곱수의 합 c++ // dp 2차원 to 1차원, 수학으로 시간복잡도줄이기 (0) | 2024.04.16 |
백준 1912 연속합 c++ // dp, 규칙발견, ox를 그때그때 선택해버리기 (0) | 2024.04.15 |
백준 11053 LIS c++ // dp, 규칙발견, 일반화 (0) | 2024.04.15 |
백준 1520 내리막길 c++ // top-down dp, dfsDp, 상하좌우탐색 문제점 (0) | 2024.04.10 |