[Java][11052] 카드 구매하기

문제:

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

11052번: 카드 구매하기

코드:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [] dp = new int[1001];

        for(int i=1;i<=n;i++){
            dp[i] = sc.nextInt();
        }

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

ex)

dp[10] = Math.max(dp[10-1]+dp[1],dp[10]) 
dp[10] = Math.max(dp[10-2]+dp[2],dp[10])  
dp[10] = Math.max(dp[10-3]+dp[3],dp[10])  
dp[10] = Math.max(dp[10-4]+dp[4],dp[10])  
dp[10] = Math.max(dp[10-5]+dp[5],dp[10])

10 = 10+0 , 9+1, 8+2, 7+3, 6+4, 5+5
위 값을 모두 비교하여 최대값을 저장한다.