문제해석
p1=1, p2=5, p3=6, p4=7일경우 N=4개를 가지기 위한 금액은
p1으로 4개를 살경우 4원, p2 1개, p1 2개를 사면 7원, 최대금액은 p2를 2번구매하는 10원의경우이다. 이 경우를 찾으면된다.
DP
가장 먼저 생각난건 백트래킹이다. 하지만 시간초과가 날거같았고 DP로도 풀수 있는 문제이다.
DP[x]=y , x:카드의 개수, y:총 가격
점화식
for (int i = 1; i <= N; i++)
{
cin >> P[i];
for (int j = i; j <= N; j++)
{
DP[j] = max(DP[j], DP[j - i] + P[i]); // dp초기값 0
}
}DP[j] = max(DP[j], DP[j - i] + P[i]);
DP[j-i]+P[i]는 Pi를 구매했을경우를 뜻하고
DP[j]는 구매하지 않았을 경우를 뜻한다.
더 큰값이 정답이므로 max를 사용했다.
이중반복문 내부 i와 j를 자세히보면
i=1, j=1 일때 DP[1]=max(DP[1],DP[0]+P[1]) = P[1] // P1을 한장 구매한경우
i=1, j=2 일때 DP[2]=max(DP[2],DP[1]+P[1]) = DP[1]+P[1] // P1을 두장 구매한경우
...
i=2, j=3 일때 DP[3]=max(DP[3],DP[1]+P[2]) // DP[3]는 p1을 세장, DP[1]+P[2]는 p1 한장, p2 한장을 구매한경우를 뜻한다.
...
그렇게 가격을 비교하여 어떤가격이 가장 비싼지 찾을수 있다.
