728x90
반응형
이 문제는 전형적인 DP 문제이다.
포인트는 N개의 카드팩을 사는데 가장 비싼 값을 반환하는 것이다.
이 곳에는 DP 배열과 P 배열을 변수로 사용한다.
DP 배열은 n개의 카드팩을 사는 방법 중 가장 큰 돈으로 살 수 있는 경우를 저장한다.
P 배열은 카드 n개가 포함된 카드팩의 값을 저장한다.
예를 들어보자,
카드팩을 4개 산다고 가정했을 때
DP[4] = max(
P[4] + DP[4 - 4 = 0],
P[3] + DP[4 - 3 = 1],
P[2] + DP[4 - 2 = 2],
P[1] + DP[4 - 1 = 3]
)
가 되고,
이를 구하기 위해선 DP[0], DP[1], DP[2], DP[3]을 필요로 하게 된다.
그럼 이를 식으로 표현해보면,
DP[N] = max(P[N] + DP[N - i], DP[N])이 되고,
반복문을 통해 DP[0], DP[1], DP[2], DP[3]를 구한다.
그러면
for(int j = 1; j <= i; j++){
dp[i] = max(dp[i], dp[i - j] + p[j]);
}
이렇게 표현할 수 있다.
코드는
// 카드 구매하기
#include <iostream>
using namespace std;
int main(void){
int count, num;
cin >> count;
int p[10001], dp[10001] = {0};
for(int i = 1; i <= count; i++){
cin >> num;
p[i] = num;
}
for(int i = 1; i <= count; i++){
for(int j = 1; j <= i; j++){
dp[i] = max(dp[i], dp[i - j] + p[j]);
}
}
cout << dp[count];
}
https://github.com/jeongdaeun98/algorithm/blob/master/2020/20110201.cpp
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 쉬운 계단 수 (0) | 2020.11.02 |
---|---|
[algorithm] 백준 - 1,2,3 더하기 5 (0) | 2020.11.02 |
[algorithm] 백준 - 좋은 수열 (0) | 2020.10.30 |
[algorithm] 백준 - 암호만들기 (0) | 2020.10.30 |
[algorithm] 백준 - 퇴사 (0) | 2020.10.30 |