백준 11052번 : 카드 구매하기

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
    int[] p;
    int[] dp;
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        p = new int[n+1];
        dp = new int[n+1];
        for(int i=1; i<=n; i++){
            p[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<=n; i++){
            dp[i] = p[i];
            for(int j=1; j<=i; j++){
                dp[i] = Math.max(dp[i], dp[j]+dp[i-j]);
            }
        }
        System.out.println(dp[n]);
    }
    public static void main(String args[]) throws IOException {
        new Main().solution();
    }
}

dp 배열에 Pi 의 값과 i를 만드는 경우의 수의 dp의 합과 비교하여 높은 값을 저장한다.

dp[1] = P1을 저장한다.

dp[2] = dp[1] + dp[1] 과 P2 중에 높은 값을 저장한다.

dp[3] = dp[1] + dp[2] 와 P3 중에 높은 값을 저장한다.

dp[4] = dp[1] + dp[3] , dp[2] + dp[2] , P4 중에 높은 값을 저장한다.