[백준 11052] 카드 구매하기

 

입력이

4

1 5 6 7

일때

카드팩은 총 4장을 구매하고, 왼쪽부터

1카드팩을 사려면 1원이 들고 카드 갯수는 1장,

2카드팩을 사려면 5원이 들고 카드 갯수는 2장,

3카드팩을 사려면 6원이 들고 카드 갯수는 3장,

4카드팩을 사려면 7원이 들고 카드 갯수는 4장 이라는 뜻이다.

즉 4번째 카드팩을 구매하면 민규가 총 4장을 사기로 했으므로 1개밖에 못사고 7원이 든다.

 

dp 배열을 만들어서 dp[n] 에 카드를 n장 샀을때 드는 최대값을 기록하는 방식으로 풀것이다.

dp 배열과 연산할 배열 pack[] 를 만들고 카드를 n장 살때 드는 비용을 기록한다. (위의 예로 들면 1,5,6,7)

 

점화식을 구해보자. (편의상 dp[0]=0, card[0]=0 으로 했다)

 

dp[1] = pack[1];

dp[2] = max(dp[1] + pack[1], dp[0] + pack[2])

dp[2] = max(dp[2] + pack[1], dp[1] + pack[2], dp[0] + pack[3])

.....

 

dp[n] = max(dp[n], dp[n-k] + pack[k])

 

k 값이 변할때 이미 dp[n]에 현재의 최대값을 저장해 놓았으므로 dp[n] 과  dp[n-k] + pack[k] 를 비교한다.

dp[n] 을 구할때 이미 dp[n-1] 에서 n-1개 카드를 뽑을때의 최대값을 구해놓았으므로

n이 감소할때마다 더 큰 카드팩을 꺼내면 된다.

 

 

 

    public static int compare(int a, int b) {
        return a > b ? a : b;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int pack[] = new int[n+1];
        int dp[] = new int[1001];
        
        pack[0] = 0; dp[0] = 0;
        for(int i=1; i<=n; i++)
            pack[i] = sc.nextInt();
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=i; j++) {
                dp[i] = compare(dp[i], dp[i-j] + pack[j]);
            }
        }
        
        System.out.println(dp[n]);
        sc.close();
    }