백준)11052.카드구매하기 - 풀이(JAVA)

처음에는 n보다 작은 자연수들을 더해서 n을 만드는 경우를 구해야 한다고 생각했다. 

그런 방향으로 풀다가 시간초과가 나버렸고 구글링 끝에 간단한 방법이 있어 정리해본다.

 

카드 n개를 구매하는 방법은.

n개가 들어있는 팩을 구매하거나, 또는

카드 1개가 들어있는 팩을 구매하고 n-1개가 들어있는 팩을 구매한다.

카드 2개가 들어있는 팩을 구매하고 n-2개가 들어있는 팩을 구매한다.

.

.

.

이런식의 방법이 있다. 

 

가장 큰 비용으로 n개를 구매하는 방법까지 도달하기 전에 n보다 작은 카드들을 가장 큰 비용으로 구매하는 법들을 기억(memomemoization)해놓고, 이전에 구했던 값들을 이용해 n개를 가장 큰 비용으로 구매하는 법을 구하는 방식으로 접근해야 하는 문제다. (Dynamic Programming 문제의 핵심!) 

 

1. 알고리즘 

문제에 주어진 입력값으로 예를 들어보자면 

 

5

10 9 8 7 6

 

5장의 카드를 갖기 위해 지불해야 하는 최대 금액은 카드1장이 들어있는 팩을 다섯번 구매하는 것으로

알고리즘은 아래와 같이 흘러간다.

입력받은 카드팩을 저장하는 배열 cardPack[n+1]이 있고, 

각 카드를 갖기 위해 지불해야하는 최대 금액을 저장하는 배열 maxArr[n+1]이 있다. 

각 배열의 0번째 요소는 무시한다. 

 

(1) 1장의 카드를 갖기 위해 지불해야 하는 최대 금액을 구한다. 

  - maxArr[1]에 cardPack[1] = 1을 저장한다.  

(2) 2장의 카드를 갖기 위해 지불해야 하는 최대 금액을 구한다.

  - 2-1) maxArr[2]에 cardPack[1] + maxArr[2-1]를 저장한다.    

  - 2-2) maxArr[2]에 2-1)에서 저장된 값과 cardPack[2] + maxArr[2-2]를 비교하여 큰 금액을 저장한다. 

[0]인덱스에는 아무 값이 들어있지 않은데, 이 경우는 2개가 들어있는 카드팩 1개를 사는 경우를 의미한다.

여기서 이미 maxArr[1]에 (1)번 로직에 의해 1장의 카드를 갖기 위해 지불해야 하는 최대 금액이 있다는 걸 기억한다. 

(3) 3장의 카드를 갖기 위해 지불해야 하는 최대 금액을 구한다.

  - 3-1) maxArr[3]에 cardPack[1] + maxArr[3-1]를 저장한다. 

  - 3-2) maxArr[3]에 3-1)에서 저장된 값과 cardPack[2] + maxArr[3-2]를 비교하여 큰 금액을 저장한다. 

  - 3-3) maxArr[3]에 3-2)에서 저장된 값과 cardPack[3] + maxArr[3-3]을 비교하여 큰 금액을 저장한다. 

[0]인덱스에는 아무 값이 들어있지 않은데, 이 경우는 3개가 들어있는 카드팩 1개를 사는 경우를 의미한다.

여기서 이미 maxArr[1]과 maxArr[2]에 (1),(2)번 로직에 의해 해당 갯수의 카드를 갖기 위해 지불해야 하는 최대 금액이 있다는 걸 기억한다. 

.

.

이런식으로 진행 하다보면 5장의 카드를 갖기 위해 지불해야 하는 최대 금액은

cardPack[1] + maxArr[5-1]을 계산한 값 50이 저장되게 되고 이를 출력하면 된다. 

 

위 알고리즘의 핵심은 결국 카드 n장을 갖기 위해 지불해야 하는 최대 금액은 n-i장의 카드를 지불해야 하는 최대 금액들을 순서대로 계산하여 저장한 후 저장된 값들을 이용하는 것이다. 

 

 

2. 나의 풀이 

package Dynamic_Programing;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
 * Date : 20. 10. 26
 * Question.No : 백준 11052 - 카드 구매하기
 * Remark :
 */
public class Boj11052_2 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] cardPack = new int[n+1];
        int[] maxArr = new int[n+1];
        cardPack[0] = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 1 ; i <= n ; i++) {
            cardPack[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1; i <=n; i++) {
            for(int j = 1; j <=i; j++) {
                maxArr[i] = Math.max(maxArr[i],cardPack[j]+maxArr[i-j]);
            }
        }
        System.out.println(maxArr[n]);
    }

}