📝문제

카드를 사용했을 때 최댓값을 묻는 문제이므로 이전의 값을 활용하는 DP알고리즘으로 풀었다.
내가 생각한 점화식은,
i개의 카드를 살 때 최댓값 = 'j번째 카드와 i-j개의 카드를 살 때의 최댓값의 합' 과 i번째 카드의 값 중 큰 값
이다.
문제에서 n보다 더 많이 산 후에 빼는 것은 불가능하다고 했으므로
위와 같은 식으로 풀었다.

📌코드

package DP;

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

public class BOJ11052 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] cards = new int[n+1];
        for(int i = 1; i < n+1; i++){
            cards[i] = Integer.parseInt(st.nextToken());
        }

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