[알고리즘-JAVA] 백준 알고리즘 11052번 - 카드 구매하기

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

카드팩을 최대한 비싸게 사려면 어떻게 사야할까? 하는 문제이다.

처음에 인풋에는 내가 사려는 카드팩의 수가 주어지고, 두번째줄에는 차례대로 카드팩을 해당 인덱스+1만큼

샀을때 얼마나 지불해야 하는가가 나온다.

2. 나의 방식대로 문제를 재정의 하자.

d[n] = n개의 카드팩을 살때 지불해야되는 최대 비용.

p[n] = n개 카드팩을 살때 지불하는 비용.

d[n] 에 대한 점화식을 세워서 구하기.

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

재귀함수 (Top-down)이나 반복문(Bottom-UP)을 사용할 계획이다.

4. 어떻게 계산할 것인가?
1) 입력

BufferedReader를 사용해 입력받을 것이다.

 

2) 시간 복잡도 계산

d[n] 한칸을 채우는데 = O(N) (n개중 최대값 구하기)

전체 시간 복잡도 = O(N^2) (n개의 배열 채우기, n개중 최대값 구하기)

 

5. 주의할 점은 무엇인가?

시간초과! O(N^2)이다.

 

6. 풀이 과정

d[n] = n개의 카드팩을 사기 위해 지불해야하는 최대값

p[n] = n개의 카드팩을 사기 위한 비용

1개짜리 카드팩을 선택했다면, d[n-1] + p[1]

2개짜리 카드팩을 선택했다면, d[n-2] + p[2]

d[n-3] + p[3]

....

d[0] + p[n]

 

점화식 : d[n] = d[n-k] + p[k]

Bottom-UP

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

public class Main{
    public static void main (String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int d[], p[], length;

        d = new int[n+1];
        String line = br.readLine();
        StringTokenizer stk = new StringTokenizer(line, " ");
        length = stk.countTokens();
        p = new int[length+1];
        // 인풋 받기
        for (int i = 1; i <= length; i++){
            p[i] = Integer.parseInt(stk.nextToken());
        }
        // 
        d[0] = 0;
        for (int i = 1; i <= n; i++){
            int max = 0;
            for (int j = 1; j <= i; j++){
                int temp = d[i-j] + p[j];
                if (temp > max){
                    max = temp;
                }
            }
            d[i] = max;
        }
        System.out.println(d[n]);
        
    }
}

Top-Down

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

public class Main{
    static int d[];
    static int p[];
    public static void main (String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int length;

        d = new int[n+1];
        String line = br.readLine();
        StringTokenizer stk = new StringTokenizer(line, " ");
        length = stk.countTokens();
        p = new int[length+1];
        // 인풋 받기
        for (int i = 1; i <= length; i++){
            p[i] = Integer.parseInt(stk.nextToken());
        }
        System.out.println(calculate(n));
        
    }
    public static int calculate(int n){
        int max = 0;
        if (n == 0){
            return 0;
        }
        if (d[n] > 0){
            return d[n];
        }
        for (int k = 1; k <= n; k++){
            int temp = calculate(n-k)+p[k];
            if (temp > max){
                max = temp;
            }
        }
        d[n] = max;
        return d[n];
    }
}