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

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

 

풀이

1. 카드 1개가 포함된 카드팩을 사는 방법
   1. 카드 1개 들은 카드팩 사기 
2. 카드 2개가 포함된 카드팩 사는 방법
   1. 카드 1개 들은 카드팩 2개 사기
   2. 카드 2개 들은 카드팩 1개 사기
3. 카드 3개가 포함된 카드팩 사는 방법
   1. 카드 1개가 들은 카드팩 3개 사기
   2. 카드 2개가 들은 카드팩 1개 + 카드 1개가 들은 카드팩 1개 사기
   3. 카드 3개가 들은 카드팩 1개 사기

위 과정을 N까지 반복하면 된다.

코드

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

public class Main {

    static int N;
    static int[] arr;
    static int[] dp;

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

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

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

        System.out.println(solution());
    }

    static int solution() {
        for (int i = 1; i <= N; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] = Math.max(dp[i], dp[i - j] + arr[j]);
            }
        }

        return dp[N];
    }
}