https://www.acmicpc.net/problem/11052
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
dp 문제이다.
dp[i] = p[i]로 우선 채워준 다음
for (int i = 2;i <= n;i++) {
for (int j = 1; j < i; j++) {
dp[i] = max(dp[i - j] + p[j], dp[i]);
}
}
이 조건문을 통해 만약 n = 4라면
i = 2 일때
dp[2] 는 dp[1] + p[1]값과 p[2]값을 비교한 뒤 더 큰 값을 넣어주었고
i = 3 일때
dp[3] 은 이전에 구한 dp[2]의 최대값과 p[1]을 더해준 값과 dp[1] + p[2] 값, p[3]의 값을 비교한뒤 가장 큰값을 넣어준다.
마찬가지로 i = 4일 때 까지 진행해준뒤 dp[4]를 출력해 주었다.
결과는 정답!
틀릴 줄알았는데 한번에 정답이 되어 기분이 좋았다.
전체 코드는 다음과 같다.
#include <iostream>
#include <algorithm>
using namespace std;
int p[10001];
int dp[10001] = { 0 };
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
for (int i = 1;i <= n;i++) {
cin >> p[i];
}
for (int i = 1;i <= n;i++) {
dp[i] = p[i];
}
for (int i = 2;i <= n;i++) {
for (int j = 1; j < i; j++) {
dp[i] = max(dp[i - j] + p[j], dp[i]);
}
}
cout << dp[n] << "\n";
return 0;
}
dp문제를 어떻게 해결해야할지 감이 좀 잡히는거 같다.
'코딩테스트 > C++' 카테고리의 다른 글
[백준 C++] 15990번: 1, 2, 3 더하기 5 (0) | 2024.04.21 |
---|---|
[백준 C++] 16194번: 카드 구매하기 2 (0) | 2024.04.21 |
[백준 C++] 9095번: 1, 2, 3 더하기 (0) | 2024.04.21 |
[백준 C++] 11727번: 2 x n 타일링 2 (0) | 2024.04.21 |
[백준 C++] 11726번: 2 x n 타일링 (0) | 2024.04.20 |