백준 11052번 : 카드 구매하기 java

이 문제를 처음 봤을 때 저는 어떤 방식으로 문제를 해결해야 할까가 의문이었습니다.

1장짜리 카드팩으로만 N개를 살 수도 있고 1장짜리 카드팩에 2장짜리 카드팩을 몇 개 섞을 수도 있습니다.

이 모든 상황들을 백트래킹으로 풀기에는 너무 많은 시간이 걸리기 때문에 시도하기 어려웠습니다.

그래서 이 문제의 분류를 보니 다이나믹 프로그래밍이였습니다.

이렇게 경우의 수가 많아 보이는데 어떻게 다이나믹 프로그래밍으로 문제를 해결해야 하나 고민을 하다가 살 수 있는 카드의 개수에 따라서 dp를 만들면 되지 않을까 생각하였습니다.

그래서 dp[1]은 카드 1개를 살 때로 정하였고 dp[2]는 카드 2개를 살 때의 최대 비용으로 정하였습니다.

dp[2]을 정하기 위해서는 2장이 들어있는 카드팩 1개와 dp[1]과 1장이 들어있는 카드팩을 같이 사는 것 중에서 뭐가 비용이 더 큰지를 비교하였습니다.

dp[3]을 정하기 위해서는 3장이 들어있는 카드팩 1개와 dp[1]와 2장이 들어있는 카드팩, dp[2]와 1장이 들어있는 카드팩을 사는 것 중에서 비용을 비교하였습니다.

이런 식으로 사는 카드의 개수가 늘어날수록 이전의 최댓값을 이용하여 문제를 푸는 식으로 문제를 해결하였습니다.

---

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

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[] data = new int[N+1];
        int[] dp = new int[N+1];

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

        for(int i = 0; i<=N; i++){
            for(int j = 0; j<=i; j++){
                dp[i] = Math.max(dp[i], dp[i-j] + data[j]);
            }
        }

        System.out.println(dp[N]);
    }
}