백준 16194 카드 구매하기2 동적계획법 활용 2가지 풀이 ( Java )

16194번: 카드 구매하기 2

 

- Bottom-up 방식

 

import java.io.*;
 
public class Main{
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        // 구매해야하는 카드 갯수
 
        String[] temp = br.readLine().split(" ");
        int[] prices = new int[n + 1];
        // 가격 저장할 배열
 
        for (int i = 0; i < n; i++) {
            prices[i + 1] = Integer.parseInt(temp[i]);
            // String to int
        }
 
        int[] d = new int[n + 1];
        // d[i] = n개의 카드를 구매하기 위해 지불해야 하는 금액의 최소값
        // 이는 i개가 들어있는 카드팩을 샀을 때 사용한 금액 + n-i개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최소값과 같다
 
        // d[i] = d[n-i] + prices[i]
        for (int i = 1; i <= n; i++) {
            // 1개를 구매해야할 때부터 n개를 구매해야 할 때 까지
            for (int j = 1; j <= i; j++) {
                if (d[i] == 0 || d[i] > d[i - j] + prices[j]) {
                    // 초기화 값과 같거나 비교해서 작으면
                    d[i] = d[i - j] + prices[j];
                }
            }
        }
 
        bw.write(String.valueOf(d[n]));
        bw.flush();
 
    }
 
}

 

- Top-Down 방식

 

import java.io.*;
 
public class Main {
 
    public static int[] d;
    public static int[] prices;
 
    public static int buyCard(int n) {
 
        if (d[n] > 0) {
            return d[n];
            // 메모한 값이 있다면 사용
        }
 
        if (n == 1) {
            // 하나 살 때
            d[n] = prices[n];
            // 최소 가격은 prices[1] 이다
            return d[n];
        }
        // 이걸 기저 사례로 세팅
 
        for (int i = 1; i <= n; i++) {
            // n개 살 때 1개 들어있는 카드팩을 구매 + 나머지했을 때 부터
            // n개 들어있는 카드팩 하나만 구매했을 때까지
            if (d[n] == 0 || d[n] > buyCard(n - i) + prices[i]) {
                d[n] = buyCard(n - i) + prices[i];
            }
 
            // 반복하며 재귀를 내려 보내고
            // 가장 작은 걸 d[n]의 값으로 저장
        }
 
        return d[n];
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        // 구매해야하는 카드 갯수
 
        String[] temp = br.readLine().split(" ");
        prices = new int[n + 1];
        // 가격 저장할 배열
 
        for (int i = 0; i < n; i++) {
            prices[i + 1] = Integer.parseInt(temp[i]);
            // String to int
        }
 
        d = new int[n + 1];
        // d[n] = n개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최초값
        // 이는 i개가 들어있는 카드팩을 샀을 때 사용한 금액 + n-i개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최대값과 같다
 
        // d[n] = d[n-i] + prices[i]
 
        int answer = buyCard(n);
 
        bw.write(String.valueOf(answer));
        bw.flush();
 
    }
 
}

 

카드 구매하기 1과 유사하지만 이건 최소값을 구해야 한다.

즉 d[n] 이 0일 때 예외 처리를 해줘야 한다는 말 ( 없이 비교만 하면 당연히 계속 0만 들어가니까 )

 

이렇게 양수만 가지고 최소값 구하는 문제에선 그래서 배열을 -1로 초기화 해주면 좋다는데

n의 범위 자체가 1부터 시작되기에 어차피 0이 없으니 여기선 그냥 0으로 처리해줘도 무방한듯