백준 11052 - 카드 구매하기

구매하려는 카드 N이 주어졌을 때, 카드 N개를 갖기 위해 지불해야하는 금액의 최댓값을 구하는 문제이다.

 

먼저 문제를 분석해보자. 민규는 카드를 어떻게 구매할 수 있을까?

 

각 카드팩의 가격이 카드의 갯수와 함께 주어졌다. 카드 1개 p[1] = M원 카드 두개 p[2] = K원 ..

 

민규가 N개의 카드를 구매한다면, N-1개가 들어있는 카드팩을 구매하고 p[1]개를 구매해서 N개

                                                      N-2개가 들어있는 카드팩을 구매하고 p[2]개를 구매해서 N개

                                                      0개가 들어있는 카드팩을 구매하고 p[N]개를 구매해서 N개를 구매하는 경우의 수로 나누어 생각해 볼 수 있을 것이다. 

우리는 이 중에서 가장 비싸게 카드를 구매하는 방법을 찾으면 된다.

따라서 점화식은 

 

D[n] = MAX(p[i] + D[n-i])일 것이다.

 

구하는 과정에서 변하지 않는 것은 각 카드팩을 구매하는 최대비용일 것이다. 

가령 N이 2고 p1 =3 p2 =1 이라면, D[2] = 6이다.(p[1]+D[1]) 

        N이 3이고 p1=3, p2=1, p3=2라면, 이미 구한 2개의 카드팩을 사는 최대비용은 여기서도 변하지 않는다. 

        어차피 최대비용을 구하는 것이 목적이므로 p2 =1인 경우는 버려도 된다. 

       따라서 p1 =3 p2 =6 p3 =2 인 상태에서 구하는 것과 같다. D[3] = P[2] + D[1]이다. 이는 p[2] => d[1]+p[1]이므로 

        결국 처음 p1=3,p2=1,p3=2 상태에서 p1을 3번 구매하는 방법과 일치하게 된다. 

 

상태: N과 i가 필요하다 , 종료조건: n==j면 D[0] + p[n]이므로 더이상 비교할 필요 없다.

 

구현 

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    public static int[] d;
    public static int[] p;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String[] priceS = br.readLine().split(" ");
        p = new int[n+1];
        for(int i=0; i<priceS.length;i++) p[i+1] = Integer.parseInt(priceS[i]);
        d = new int[n+1];

        for(int i=1; i<=n;i++){
            for(int j=1; j<=i; j++){
                if(d[i] == 0 || d[i] <d[i-j]+p[j])
                    d[i] = d[i-j]+p[j];
            }
        }
        System.out.print(d[n]);

      }
}

 

 

--> 1 2 3 4가 있을 때 1-4, 2-3 이런식의 접근 구현하는 코드.. 외워두면 좋을 듯 하다