[BOJ] 11052 카드 구매하기 - JAVA

1. 문제

11052번: 카드 구매하기

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

---

2. 풀이

• dp[i]값은 card[i], dp[1]+card[i-1], dp[2]+card[i-2], ... , dp[i-1]+card[1] 중 가장 큰 값이다. 
• 앞선 dp배열에서 i와 인덱스가 얼마나 차이나는지 보고 그 차이만큼 card세트 가격을 더하면 된다.

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

public class BOJ_11052_카드구매하기 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      StringTokenizer st = new StringTokenizer(in.readLine());
      int[] cards = new int[N + 1];
      for (int i = 1; i <= N; i++) cards[i] = Integer.parseInt(st.nextToken());

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

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

---

3. 결과

top-down 방식으로 해보고싶었는데 위로 가든 밑으로 가든 여러 번 반복해야할 것 같아서 하지 않았다.