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

 

문제:

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

 

 

접근 : 

 

 - 카드를 최댓값으로 N개 구매하기 위해서는 1 부터 N까지 구매 최대값을 알고 있어야한다.

 

 - 카드 1개를 살때 최대값 (dp[1])은, card[1]이 최대값이다.

 

 - 카드 2개를 살때 최대값 (dp[2])은 , card[1]을 2번 구매하는 값과 card[2] 중 더 큰 값이다.

 

 - dp[3] 은, dp[1] + dp[2] 과 card[3] 중 더 큰 값이다.

 

 - dp[4] = dp[1] + dp[3] , dp[2] + dp[2], num[4] 중 가장 큰 값이다.

 

 - dp[5] = max { (dp[1] + dp[4]), (dp[2] + dp[3]), (card[5]) } 

 

 - dp[n] = max{ (dp[1] + dp[n-1]) , (dp[2] + dp[n-2]), º º º, (dp[n/2] + dp[n - n/2] ) , (card[n]) }

 

 

코드 구현 :

 

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

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[] nums = new int[n+1];
        String[] inputs = br.readLine().split(" ");
        for(int i = 1 ; i <= n ; i++) nums[i] = Integer.parseInt(inputs[i-1]);
        int[] dp = new int[n + 1];

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