[백준] 11052번 - 카드 구매하기

1. 문제 이해

입력으로 N과 Pi가 P1부터 PN 까지 순서대로 주어진다.

 

P의 인덱스를 i라고 하면,  i의 합이 N이 되는 Pi들의 최댓값을 구하는 문제이다. 즉, 집합 P에 대한 중복조합이다. 

부분집합의 합으로 정답을 구할 수 있지만 N의 최댓값이 10000이기 때문에 시간초과에 걸린다.

 

그래서 DP를 이용해서 풀어야 한다.

2. 문제 풀이

카드팩(N)은 N개의 카드가 들어있다. 카드팩(i)의 가격은 P(i)이다.

N=4이고, Pi 가 순서대로 1 1 2 3 이 주어졌다면, 다음과 같이 풀 수 있다.

 

 

N = 4 , P = { 1, 1 ,2 ,3}

• 카드팩 1개 구매

카드팩 1개를 구매하는 경우는 1가지이므로 P1, 즉 1이다.

 

• 카드팩 2개 구매

이 경우는 2가지 이다. P1 2개 혹은 P2 1개이다. 이 경우, 최댓값은 max ( 1 + 1,  1) = 2 이다. 

 

• 카드팩 3개 구매

이 경우는 3가지 이다.

 

3개묶음 1개                     2개묶음 1개 + 1개 묶음 1개,                   1개묶음 + 1개묶음 2개

계산하면, max (P3, P2+P1, P1 + P1 + P1) = 3 이다.

 

• 카드팩 4개 구매

이 경우는, 가짓수가 많다.

 

4개묶음 1개 = 3
3개묶음 1개 + 1개 묶음 1개 = 3개묶음 구매하는 경우 + 1개 묶음 = 2+1
2개 묶음 2개 = 2개묶음 구매하는 경우 + 2개묶음
1개 묶음 2개 + 2개 묶음 1개 = 1개묶음 구매하는 경우 + 2개묶음
1개 묶음 4개 = 4

이 경우, 최댓값을 바로 찾기 어렵다. 그래서 DP를 이용한 식으로 나타낸다.

 

카드팩 N개의 최댓값을 M(N)이라고 하고, 각 카드팩의 가격을 P(i) 라고 한다면

M(1) = P(1)이다.
M(2)는 P(2) 혹은 M(1) + P(1) 중 최댓값이다.
M(3)는 P(3) 혹은 max ( M(2) + P(1), M(1) + P(2) ) 중 최댓값이다.
M(4)는 P(4) 혹은 max ( M(3) + P(1), M(2) + P(2), M(1) + P(3) ) 중 최댓값이다.

M(N) = max( max( M(n-i) + P(i) ) , P(N) )

3. 코드

#include <bits/stdc++.h>
using namespace std;
int card[1001];
int ret[1001]; 
int max_price(int n){
    if(ret[n] != -1) { return ret[n]; }

    if(n == 2) { return ret[2] = max(card[2], card[1]*2);}
    int m = -1, k;
    for(int i=1; n - i > 0; i++){
        k =  max_price(n-i) + card[i];
        if( k > m ) { m = k;}
    }
    return ret[n] = max( m , card[n] );
}
int main(){
    int N;
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%d",&card[i]);
    }
    memset(ret,-1,sizeof(ret));
    ret[1] = card[1];
    printf("%d\n",max_price(N));
}