JAVA)11052번 카드 구매하기 - 다이나믹 프로그래밍

해당 문제를 위한 알고리즘을 해결해야 하는 부분 문제의 수가 n(카드 개수)개, 

각 부분 문제를 해결하기 위해 총 n개의 수를 비교해서 그 중 최대값을 구해야 하므로 부분 문제당 O(n)의 시간이 소요된다.

결국 O(n^2)의 시간복잡도를 갖는다.

 

1. Top-Down 방식

import java.util.*;

public class Main {
    static int[] A; // 해당 인덱스 개수의 카드를 구매하는 최대 금액
    static int[] P; // 인덱스 개수의 카드를 포함하는 카드팩의 가격
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cardNum = sc.nextInt();
        P = new int[cardNum+1];
        A = new int[cardNum+1];
        for (int i=1;i<cardNum+1;i++) {
            P[i] = sc.nextInt(); // 각 카드 팩의 가격 받아오기
        }
        System.out.println(maxPrice(cardNum));
    }

    static int maxPrice(int num) {
        // Top-Down 방식
        // A[n] = n개의 카드를 구매하는 최대 금액, P[i] = i개의 카드를 포함하는 카드팩의 가격
        // 점화식 : A[n] = max(A[n-1] + p[i])
        if (num < 1) {
            return A[num];
        }
        if (A[num-1] == 0) {
            A[num-1] = maxPrice(num-1);
        }
        for (int i=1;i<num+1;i++) {
            if (A[num] < A[num-i] + P[i]) {
                A[num] = A[num-i] + P[i];
            }
        }
        return A[num];
    }

}

 

2. Bottom-Up

import java.util.*;

public class Main {
    static int[] A; // 해당 인덱스 개수의 카드를 구매하는 최대 금액
    static int[] P; // 인덱스 개수의 카드를 포함하는 카드팩의 가격
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cardNum = sc.nextInt();
        P = new int[cardNum+1];
        A = new int[cardNum+1];
        for (int i=1;i<cardNum+1;i++) {
            P[i] = sc.nextInt(); // 각 카드 팩의 가격 받아오기
        }
        System.out.println(maxPrice(cardNum));
    }

    static int maxPrice(int num) {
        // Bottom-Up 방식
        // A[n] = n개의 카드를 구매하는 최대 금액, P[i] = i개의 카드를 포함하는 카드팩의 가격
        // 점화식 : A[n] = max(A[n-1] + p[i])
        A[1] = 1;
        for (int i=1;i<num+1;i++) {
            for (int j=1;j<i+1;j++) {
                if (A[i] < A[i-j] + P[j]) {
                    A[i] = A[i-j] + P[j];
                }
            }
        }
        return A[num];
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/11052