[백준저지] 11052번 : 카드 구매하기

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

1. 문제

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오.

 

입)

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

 

출)

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

2. 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        // 구매하려고 하는 카드 수
		int cnt = sc.nextInt();
        // 구매하려고 하는 카드 수
        int[] p = new int[cnt+1];
        int[] d = new int[cnt+1];
        // 금액 세팅
        for (int i = 1; i <= cnt; i++) {
            p[i] = sc.nextInt();
        }
        for (int i = 1; i <= cnt; i++) {
            for (int j = 1; j <= i; j++) {
                int temp = p[j] + d[i-j];
                // 최대값인지 비교
                if (temp > d[i]) {
                    d[i] = temp;
                }
            }
        }
        System.out.println(d[cnt]);
    }
}

D[i] => 카드 i개를 구매했을 때 금액 최대값

카드 i개를 구매하는 방법은 => 카드 j개가 들어있는 카드팩을 구매하고, 카드 i-j개를 구매

위 식을 이용해서 최대가 되는 값을 찾는다.

D[i] = max(D[i-j] + P[j]), 1<= j <= i

이 식으로 해결.