문제

BOJ 11052: 카드 구매하기 https://www.acmicpc.net/problem/11052

풀이

조건

• 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.
• 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다.
• N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구한다.

풀이 순서

• DP로 해결한다.
• i개의 카드를 사야할 때
  • 1개를 구입하고 i - 1개를 구입
  • 2개를 구입하고 i - 2개를 구입
  • 3개를 구입하고 i - 3개를 구입
  • ...
  • i개를 구입하고 0개를 구입

코드

Java

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

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[] cards = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        // 카드 i개 구입할 때의 가격 기록할 DP 배열
        int[] dp = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = Math.max(dp[i], dp[i - j] + cards[j]);
            }
        }

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

정리

• DP 문제처럼 규칙을 찾고 점화식을 찾아야 한다는 것은 알았지만 식을 못 세워서 시간이 오래걸렸다.