카드 구매하기 ( 백준 11052 )

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

 

* dp 문제이다.

* 인덱스가 카드 갯수이고 값이 가격이다

* pack[1]의 뜻은 카드팩 1개를 지불해야하는 금액

* dp[1]의 뜻은 카드팩 1개를 지불해야하는 최대 금액 (최댓값)

* 카드 N개 구매시 최댓값을 계산

* 차례대로 카드 1개 구매시 최댓값을 dp 배열에 저장 후 출력

 

 

* 점화식은 Math.max(dp[i], pack[j] + dp[i-j])

* j+(i-j)개의 최댓값을 갱신하면 된다. 즉 i개의 최댓값을 인덱스 별로 계산.

 

import java.io.*;
import java.util.*;

public class BOJ11052 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        int[] pack = new int[size+1];
        int[] dp = new int[size+1];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 1; i <= size; i++) {
            pack[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1; i <= size; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] = Math.max(dp[i], pack[j] + dp[i-j]);
            }
        }

        System.out.println(dp[size]);
    }
}

 

* 여기서 2중 for 루프를 주목.

* i는 총 i개의 팩을 구매한다는 뜻

* j는 현재 j개의 팩을 선택한다는 뜻

* Math.max(dp[2], pack[1] + dp[1]) 뜻은 

총 2개의 팩을 구매예정이고 1개의 pack을 지불해야하는 금액, 1개의 pack을 구매할때 지불하는 최댓값.

* 이렇게 인덱스를 돌려가며 계산해서 최댓값을 dp[i]에 할당 끝.