https://www.acmicpc.net/problem/11052
🔎 해결 방법
예를 들어 민규가 구매하고자 하는 카드의 개수가 4개라면,
가능한 조합은
4 / 3 + 1 / 2 + 2 / 2 + 1 + 1 / 1 + 1 + 1 + 1 이므로
자연수의 분할로 접근하면 되는 줄 알았다.
그러면 각 경우는 위와 같이 계산하면 되는데 2 +2 가 문제였다.
dp를 생각하지 못하고 2 + 2를 계속 p[2] + p[2]라고 계산하는 바람에 점화식을 세울 수 없었다.
하지만!
2 + 2를 dp[2] + p[2] 라고 생각하면 규칙이 보인다.
즉, 카드 4개를 사고 싶다면
- 카드 4개가 포함된 카드팩(p[4]) + 카드 0개를 구매하기 위한 최댓값(dp[0])
- 카드 3개가 포함된 카드팩(p[3]) + 카드 1개를 구매하기 위한 최댓값(dp[1])
- 카드 2개가 포함된 카드팩(p[2]) + 카드 2개를 구매하기 위한 최댓값(dp[2])
- 카드 1개가 포함된 카드팩(p[1]) + 카드 3개를 구매하기 위한 최댓값(dp[3])
위의 4가지 경우를 모두 고려해주고, 가장 큰 값을 max 에 저장하면서 진행하면 된다.
이때 2번과 4번이 같은 경우가 아닌지 궁금할 수 있는데, p[3]과 dp[3]이 같지 않은 경우가 있기 때문에 나눠서 계산해줘야 한다!
💡 내 코드(C++)
// [11052] 카드 구매하기
// https://www.acmicpc.net/problem/11052
#include <iostream>
using namespace std;
int p[10001];
int main(void)
{
int dp[1001];
int n; // 민규가 구매하려고 하는 카드의 개수
int max; // 지불해야 하는 금액의 최댓값
cin >> n;
for(int i = 1 ; i <= n ; i++) {
cin >> p[i];
}
p[0] = 0, dp[0] = 0, dp[1] = p[1];
for(int i = 2 ; i <= n ; i++) {
max = dp[1];
for(int j = i ; j > 0 ; j--) {
if(p[j] + dp[i-j] > max) {
dp[i] = max = p[j] + dp[i-j];
}
}
}
cout << dp[n] << endl;
}
반응형
'Baekjoon > DP' 카테고리의 다른 글
[11048] 이동하기 (0) | 2020.05.24 |
---|---|
[14501] 퇴사(C++) (0) | 2020.05.23 |
[1003] 피보나치 함수(C++) (0) | 2020.04.05 |
[10844] 쉬운 계단 수 (0) | 2020.04.05 |
[2225] 합분해(C++) (0) | 2019.09.15 |