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

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제 링크는 여기를 참조

 

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

 

 

카드 N개 구매 시, 최대의 비용을 구하는 문제

 

 

2. 풀이

 

이 문제는 DP로 해결할 수 있다. 우선 문제를 이해해보자.

카드 N개를 구매하고자 하는데, 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] = MAX(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]);
        }
        
        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.max(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]);
        }
        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.max(temp, current);
        }
        return dp[n] = temp;
    }
}

 

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