알고리즘 풀이 - 백준 16194(카드 구매하기 2, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조
비슷한 문제인 11052번(카드 구매하기) 포스팅은 여기를 참조

 

 

1. 문제

 

문제 링크는 여기를 참조

 

문제 내용을 보려면 아래 더보기 클릭

 

이번 문제는 16194번과 비슷한데 그 상태에서 최대값이 아닌 최소값을 구하는 방향으로 바뀐 것이다.
즉, 카드 N개 구매 시, 최소의 비용을 구하는 문제

 

 

 

2. 풀이

 

이 문제 또한 이전의 포스팅 문제와 같이 DP로 풀 수 있다.

카드 N개를 구해하는데, i번째 카드팩에는 i개의 카드가 있으며 i번째 카드팩의 가격을 P[i]라고 부르자. 이 때, N개의 카드를 원하는 경우 그 비용의 최소값이 DP[N]이라고 부르자.

 

그렇다면, N개의 카드를 구매하는 경우의 수는 다음과 같을 것이다.

1) P[N] : N번째 카드팩만 구매하는 경우
2) DP[1] + P[N-1] : N-1번째 카드팩을 구매하고 1개의 카드팩을 사는 경우의 수 중 가장 최소의 비용인 경우
3) DP[2] + P[N-2] : N-2번째 카드팩을 구매하고 2개의 카드팩을 사는 경우의 수 중 가장 최소의 비용인 경우
...
N-1) DP[N-1] + P[1] : 1번째 카드팩을 구매하고 N-1개의 카드팩을 사는 경우의 수 중 가장 최소의 비용인 경우

그렇다면, 위의 경우의 수 중 최소값인 경우만 구하면 전체 답을 구할 수 있게 된다.

 

매 번 문제를 구할 때마다 DP[N-i]의 경우를 참조해야 하며 그 답이 변하지 않고 그대로 사용될 수 있으므로 DP의 두 가지 조건인 Overlapping Subproblems와 Optimal Substructure를 만족한다.

 

그렇다면, DP로 풀 수 있으니 저장할 State의 정의를 다시 한 번 세워보자. 아래와 같을 것이다.
정의 : DP[N] = N개의 카드를 구매하기 위한 최소 비용

N 하나 만이 변수이므로 1차원의 배열을 통해 상태 저장이 가능할 것이다. 기저 상태와 점화식을 세워보자.
카드팩의 가격은 상태 변화가 아니라 주어지는 값이므로 별도의 배열을 통해 저장하기만 하면 된다.

기저 상태는 N이 1인 상태이다. N=1일 때는 1개 짜리 카드팩 하나만 사는 경우만 가능하다.
기저 상태 : DP[1] = P[1]

점화식은 아래와 같다.
점화식 : DP[n] = MIN(DP[i], DP[i-j] + P[j]) {for i from 0 to n-1}

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[] p;
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        String s[] = br.readLine().split(" ");
        
        p = new int[n+1];
        dp = new int[n+1];
        
        for(int i=1; i <= n; i++){
            p[i] = Integer.parseInt(s[i-1]);
            dp[i] = Integer.MAX_VALUE; // 우선 최대값으로 초기화하고 더 작은 값으로 업데이트
        }
        
        System.out.println(bottomUp(n));
        br.close();
    }
    
    // Bottom-up 방식
    public static int bottomUp(int n){ 
        // 기저 상태는 카드팩 1개만 구매하는 경우
        dp[1] = p[1];
        
        // 반복문을 통해 점화식을 구성하여 최소값을 채워나감
        // 최초에는 p[i]로 i번째 하나만 사는 경우로 지정
        for(int i=2; i <= n; i++){
            dp[i] = p[i];
            for(int j=1; j <= i; j++){
                dp[i] = Math.min(dp[i-j] + dp[j], dp[i]);
            }
        }
        return dp[n];
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[] p;
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        String s[] = br.readLine().split(" ");
        
        p = new int[n+1];
        dp = new int[n+1];
        
        for(int i=1; i <= n; i++){
            p[i] = Integer.parseInt(s[i-1]);
            // Bottom-up과 달리 Integer.MAX_VALUE로 초기화 하지 않음.
            // 왜냐하면, topDown으로 내려가면서 p[n]과 비교하는 작업을 수행하기 때문
        }
        dp[1] = p[1]; // 기저 상태 설정
        
        System.out.println(topDown(n));
        br.close();
    }
    
    // Top-down 방식
    public static int topDown(int n){
        if(dp[n] > 0) return dp[n];     // 값이 이미 있었다면 바로 반환
        
        int temp = p[n]; // 비교 전 최초에는 n개 짜리로 지정
        for(int i=1; i <= n; i++){
            int current = topDown(n-i) + p[i];
            temp = Math.min(temp, current);
        }
        return dp[n] = temp;
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.