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

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

---

1. 풀이

보통 DP의 경우 경우의 수를 구하는 경우가 많아

 

처음엔 다른 방식으로 풀어보다 백준 강의를 통해 DP로 푸는 방법을 알 수 있었다.

 

카드 N개를 구매하는데 드는 비용의 최대값을 구하면 되는 문제이다.

 

이를 점화식으로 표현하기위해서 다음과 같은 식이 나온다.

 

카드 N개의 최대비용을 구한다면, 아래식을 반복하면서 최대값을 구한다.

• 카드 1개가 들어있는 카드팩을 구매한다면, 카드 N-1개를 구매한다.
• 카드 2개가 들어있는 카드팩을 구매한다면, 카드 N-2개를 구매한다.
• . . .
• 카드 i개가 들어있는 카드팩을 구매한다면, 카드 N-i개를 구매한다.

주의할 점은 카드 N-i개를 꼭 N-i개가 들어있는 카드팩을 사는 것이 아니다. 여러개의 카드팩을 구매하여 N-i개를 구매하면 된다.

( 예를 들어, 4개를 사는데 1+3이라면, 1+(1+1+1)이 될 수도 있는 것이다. )

 

코드로 점화식을 세우면 아래와 같다.

 

// N개의 카드를 사는데 최대 비용 = N-i개의 카드를 사는데 최대 비용 + i개짜리 카드팩 비용.

D[N] = D[N-i] + P[i];

---

2. 코드

import java.util.*;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] p = new int[1001]; // 카드팩 p[i] : i개 카드가 들어있는 카드팩.
        int[] D = new int[10001]; //
        for(int i = 1; i <= N; i++)
            p[i] = sc.nextInt();

        // 카드 1개부터 N개까지. ( Bottom-Up 방식 )
        for(int i = 1; i <= N; i++){
            // 카드 팩 1개부터 i개까지
            for(int j = 1; j <= i; j++){
                D[i] = Math.max(D[i] , D[i-j] + p[j]);
//                if(D[i] < D[i-j] + p[j])
//                    D[i] = D[i-j] + p[j];
            }
        }

        System.out.println(D[N]);
        sc.close();
    }
}