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

 

11052번: 카드 구매하기

 

카드를 N개 구매하였을 때 지불해야 하는 금액의 '최댓값'을 구하는 문제이다. 카드 N개를 구매하는 모든 경우의 수를 고려하되, 한 번 계산한 결과를 메모제이션 하는 다이나믹 프로그래밍을 사용하여 처리 시간을 줄인다.

 

N = 3인 경우를 살펴보자.

 

3개의 카드를 구매하는 경우의 수는

*1개가 포함된 카드팩 P1을 3개 구매하는 경우

*2개가 포함된 카드팩 P2 1개와 1개가 포함된 카드팩 P1 1개를 구매하는 경우

3개가 포함된 카드팩 P3 1개를 구매하는 경우

 

세 가지 경우의 수 중에서 최대 비용에 해당하는 값이 dp에 저장된다.

 

여기서 *표시된 두 경우의 수를 다르게 표현하면 N-1개의 카드를 구매하는데 드는 비용의 최댓값 dp[2]에 P1 한 개를 추가로 구매하는 비용이라고도 볼 수 있다. 즉 P1 카드팩 두 개를 구매하는 경우와 P2카드팩 하나를 구매하는 경우 중 더 큰 비용을 dp[2]에 저장한다.

 

이를 Top-Down 방식을 사용하여 표현하면 아래와 같다.

 

static int recur (int N) {
        
    if (dp[N] == null) {
        	
        dp[N] = P[N];
            
        int idx = 1;

        while (N - idx > 0) {
            dp[N] = Math.max(dp[N], recur(N-idx) + P[idx]);
            idx++;
        }
    }

    return dp[N];
}

 

 

 

 

전체 코드

 

 

Top-Down 방식

import java.util.*;

public class Main {
    
    static int[] P;
    static Integer[] dp;
    
    public static void main (String[] arg) {
        
        Scanner sc = new Scanner(System.in);
        StringTokenizer st = null;
        int max = 0;
        
        int N = Integer.parseInt(sc.nextLine());
        
        P = new int[N+1];
        dp = new Integer[N+1];
        
        st = new StringTokenizer(sc.nextLine(), " ");
        
        for (int i=1; i<N+1; i++) P[i] = Integer.parseInt(st.nextToken());
        
       	dp[0] = 0;
        
        System.out.println(recur(N));
        
        sc.close();
    }
    
    static int recur (int N) {
        
        if (dp[N] == null) {
        	
            dp[N] = P[N];
            
            int idx = 1;
            
            while (N - idx > 0) {
                dp[N] = Math.max(dp[N], recur(N-idx) + P[idx]);
                idx++;
            }
        }
        
        return dp[N];
    }
}

 

 

Bottom-Up 방식

import java.util.*;

public class Main {
    
    static int[] P;
    static Integer[] dp;
    
    public static void main (String[] arg) {
        
        Scanner sc = new Scanner(System.in);
        StringTokenizer st = null;
        int max = 0;
        
        int N = Integer.parseInt(sc.nextLine());
        
        P = new int[N+1];
        dp = new Integer[N+1];
        
        st = new StringTokenizer(sc.nextLine(), " ");
        
        for (int i=1; i<N+1; i++) P[i] = Integer.parseInt(st.nextToken());
        
        dp[0] = 0;
        
        for (int i=1; i<N+1; i++) {
            dp[i] = P[i];
            for (int j=1; j<i; j++) {
                dp[i] = Math.max(dp[i], dp[i-j] + P[j]);
            }
        }
        
        System.out.println(dp[N]);
        
        sc.close();
    }
}