[백준] 카드 구매하기 - 11052

문제설명

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

 

기본아이디어

N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구해라.

문제를 읽고 N의 최대값을 구하려면 어떤 값들과 비교 해야하는지를 고민해 보았다. 동적계획법으로 카드를 N개 구하기 이전에 카드를 N-1개 고르는 값이 최대값으로 다 구해져있다고 가정을 한다면 N개를 뽑는 경우의 수(비교해야되는 수는)

C(1) + C(N-1), C(2) + C(N-2), C(3) + C(N-3) , ... , C(N/2) + C(N/2) 

( N=2의배수 가정, C(X)는 카드 X개를 뽑는 최대비용)

과 처음에 제시해준 Pn을 전부 다 같이 비교해서 최대값을 구하면 카드 N개를 뽑는 최대값을 보장할 수 있다.

 

구현코드

 public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(input.readLine());
        int[] cardPack = new int[N+1];
        StringTokenizer st = new StringTokenizer(input.readLine());
        for(int i = 1; i <= N; i++)
            cardPack[i] = Integer.parseInt(st.nextToken());
 
        int[] maxPrice = new int[N+1];
        for(int i = 1; i <= N; i++){
            maxPrice[i] = cardPack[i];
            for(int j = 1; j <= i/2; j++){
                int temp = maxPrice[j] + maxPrice[i-j];
                if(temp > maxPrice[i])
                    maxPrice[i] = temp;
            }
        }
        System.out.println(maxPrice[N]);
    }

 

정리, 기억할 내용

1. 그림을 그려보자.2. N을 보고 가능한지 러프하게 계산해보자.