백준 11025 - 카드 구매하기

깃허브:

https://github.com/MSIQOC/BOJ/blob/master/b11042_%EC%B9%B4%EB%93%9C%EA%B5%AC%EB%A7%A4%ED%95%98%EA%B8%B0.java

 

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

민규가 구매하려고 하는 카드의 개수 N과 카드가 i개 포함된 카드팩의 가격 Pi원이 주어지면 N개를 구매하기 위해 지불해야하는 최대 금액을 출력하는 문제이다.

위의 예제 입력에서는 총 4개의 카드를 최대값으로 사야한다. 다이나믹 프로그래밍은 작은 해답을 통해서 점차 큰 해답으로 천천히 다가가는 것이다. 4개를 구매할 때 지불해야하는 최대 금액을 찾기 위해서는 먼저 1개를 구매할 때 지불할 수 있는 최댓값을 찾는다. 그것을 D라고 한다면 D[1] = 1이 된다. 카드 두개를 구매하기위해 지불해야하는 최대값을 구하기 위해서는 1개를 구매할 때 지불가능한 최대값에 한개를 더 구매하거나 바로 카드팩 두개짜리를 구매하는 방법이 있다. 즉, max(D[1]+P[1], P[2])를 구하면 되고, 이것이 D[2]가 된다. 카드 세개를 구매하는 경우에는 하나를 구매하는 최댓값에 카드팩 두개짜리를 사거나, 두개를 구매하는 최댓값에 카드팩 한개짜리를 사거나, 바로 카드팩 세개짜리를 사는 방법이 있다. 이것을 식으로 나타내면 max(D[1]+P[2], D[2]+P[1], P[3])이 된다.

이렇게 해서 카드 네개를 구매할 때 지불할 수 있는 최댓값은 D[2]+P[2]인 10이 된다.

 

import java.io.*;
import java.util.StringTokenizer;
public class b11042_카드구매하기 {
    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());
        int P[] = new int[n+1];
        int D[] = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; ++i)
            P[i] = Integer.parseInt(st.nextToken());
        D[1] = P[1];
        for(int i=2; i<=n; ++i) {
            int m = P[i];
            for(int j=1; j<=i; ++j) {
                m = Math.max(m, D[j]+P[i-j]);
            }
            D[i] = m;
        }
        bw.write(D[n]+"\n");
        bw.flush();
    }
}