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

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

11052번: 카드 구매하기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];
        dp[1] = 1;

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<=n; i++){
            for(int j=i; j>=1; j--){
                dp[i] = Math.max(dp[i], dp[i-j]+arr[j]);
            }
        }
        System.out.println(dp[n]);
    }
}

 

 

 

dp[n] = n개 카드를 살 경우의 최대 금액

 

여기까진 생각했는데 그 이후에 점화식을 세우는게 어려웠다.

 

i+j = n개 라고 하면, 

카드 i개를 사기위한 최대 금액 dp[i]와 j개짜리 카드팩 값을 더한 값의 최댓값을 구하면 되는 것이였다. 

 

 

예를 들어 n = 4일때, 

dp[4] = 

카드 0개를 사기위한 최대 금액 + 4개짜리 카드팩 값

카드 1개를 사기위한 최대 금액 + 3개짜리 카드팩 값

카드 2개를 사기위한 최대 금액 + 2개짜리 카드팩 값

카드 3개를 사기위한 최대 금액 + 1개짜리 카드팩 값

 

이 네가지 경우를 모두 비교해 제일 큰 값을 구하면 된다.