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

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

11052번: 카드 구매하기

---

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

public class Main {
    static int N;
    static int[] cardPack;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        cardPack = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            cardPack[i] = Integer.parseInt(st.nextToken());
        }
        int[] dp = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                if(i > j) continue;
                dp[j] = Math.max(dp[j], dp[j - i] + cardPack[i]);
            }
        }
        System.out.println(dp[N]);
    }
}

💡 DP

풀이

• 처음에는 그리디를 사용해 풀려고 했는데 반례 존재함 = 카드 1장 별 가치로 정렬해도 유효하지 않음,,,

5  // 1 9 18 25 1 => 정답 27 (2 + 3) / 출력 26 (1+4)

• 가치의 차이가 명확하게 정해져 있지 않을 때는 그리디가 패착!!! DP로 경로를 돌리자..ㅎ

---

• 0/1 knapsack 생각해서 복잡하게 풀다가 겁나 꼬였다..ㅎㅎ 그냥 단순하게 푸는게 답
• 해당 카드를 담는 경우 VS 담지 않는 경우 최댓값을 구하자
  • dp[구매한 카드 개수] 로 현재 누적 카드 개수가 j개인 상황에서 i개 팩을 사는/사지 않는 경우에 대해 최대 값을 갱신하는 것