백준 11052 카드 구매하기 Java

정답률이 59퍼센트인 dp문제이다. 역시 dp문제는 나같은 초보자에게는

정답률과 상관없이 점화식을 떠올리기 참 힘든 문제인 것 같다.

 

문제를 간단히 설명하자면

민규가 N개의 카드를 갖기 위해 지불해야 하는 최대 금액을 출력하는 문제이다.

 

입력으로는 갖기 위한 카드개수 N개와

1장이 들어있는 카드팩 가격

2장이 들어있는 카드팩 가격

.

.

.

N장이 들어있는 카드팩 가격이 주어진다.

 

예를 들어 N이 18이라면

정답은

16장이 들어있는 카드팩 가격 + 2장이 들어있는 카드팩 가격 이 될 수 도 있고

15장 + 3장

14장 + 4장

여러가지 경우의 수가 있다.

dp로 풀어야하는 전형적인 문제이다.

 

점화식을 열심히 고민해봤지만 이번에도 역시 떠올리지 못했다.

정답은 위에서 말한 것 처럼

이중 for문을 사용해서 전부 비교해보면 되는 것이었다.

왜 그 생각을 못했을까..

 

dp[i]에는 i장의 카드를 살 경우의 최대금액이다.

dp[5]인 경우에는

4장을 사기위한 최대 값 + 1장 팩 값

3장을 사기위한 최대 값 + 2장 팩 값

2장을 사기위한 최대 값 + 3장 팩 값 

1장을 사기위한 최대 값 + 4장 팩 값

중에 가장 큰 수가 들어가는 것이다.

 

dp는 정말 생각해내기 어렵다.

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] a = new int[n+1];
        int [] dp = new int[n+1];
        
        for(int i=1; i<=n; i++)
            a[i] = scan.nextInt();
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = Math.max(dp[i], dp[i - j] + a[j]);
            }
        }
        System.out.println(dp[n]);
    }