오답노트
[DP] BOJ 11052 카드 구매하기 본문
https://www.acmicpc.net/problem/11052
- 문제 파악
정수 N 과 P1~PN 의 정수가 주어진다. 1~N 을 적절히 조합하여 N을 만드는 수의 조합에서 Pi들의 합이 최대값을 출력하라.
-정답
1. 경우의 수
모든 경우의 수를 살펴 보지 않고 D[i-1] + D[1]만 확인했었다.
점화식을 찾는 도중 D[i-1] + D[1] = D[i-2] + D[2] 를 찾았고, 시간 초과를 염려해서 2중for문을 기피하려고 했다.
하지만 위 점화식은 여러 조합이 있을때는 매우 취약했다.
2. D[i] = tmp; - > D[i] = max(tmp, D[i]);
모든 경우의 수를 도는 만큼 이미 최대값이 D[i] 에 있음에도 그보다 작은 값이 입력되는 경우가 있었다.
시간 초과를 두려워 하지말자.
디버깅을 좀 더 꼼꼼히 하자.
#include "bits/stdc++.h"
using namespace std;
int D[1002]; // 팩의 개수에 대한 최대값
int arr[1002]; // 입력 : 팩의 개수에 대한 값
int n;
int ans;
int main()
{
cin >> n;
cin >> arr[1];
D[1] = arr[1];
for (int i = 2; i <= n; i++)
{
cin >> arr[i];
for (int j = 0; j <= i / 2; j++)
{
int a = i - j;
int b = i - a;
int tmp = D[a] + D[b];
if (tmp < arr[i])
{
D[i] = arr[i];
}
else
{
D[i] = max(tmp, D[i]);
}
ans = max(tmp, ans);
}
if(D[1] * i > D[i])
ans = max(D[1]*i, ans);
}
ans = max(D[n], ans);
cout << ans;
return 0;
}
'C,C++ > 코딩테스트' 카테고리의 다른 글
[DP] 15990 1, 2, 3 더하기 5 - 오답노트 (0) | 2022.05.10 |
---|---|
[DP] BOJ 16194 카드 구매하기 2 (0) | 2022.05.10 |
[DP] BOJ 11727 2Xn 타일링 2 - 오답노트 (0) | 2022.05.09 |
[비트마스크] BOJ 1182 부분수열의 합 (0) | 2022.05.09 |
[비트마스크] BOJ 11723 집합 (0) | 2022.05.08 |