[백준] JAVA 자바 : 카드 구매하기 (11052번)

 

---

N개의 카드를 구매하기 위해서는 price[N]의 가격과 dp[N-i] + dp[i] (i <= N)을 반복 비교하여 최댓값/최솟값을 구할 수 있다.
사실 이게 글로 작성하기는 되게 애매해서… 아래 코드를 보고 DP를 조금만 이해한다면 쉽게 해결할 수 있을 것이다.

 

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

public class BuyingCards {

    static int[] dp;
    static int[] price;

    public static int stoi(String str) {
        return Integer.parseInt(str);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = stoi(br.readLine());
        dp = new int[N+1]; // 금액의 최댓값을 저장하는 dp 배열
        price = new int[N+1]; // 가격 Pi를 저장하는 배열

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i=1; i<=N; i++) {
            price[i] = stoi(st.nextToken());
        }

        dp[1] = price[1];
        for (int i=2; i<=N; i++) {
            int max = price[i]; // N개를 한 번에 살 수 있는 가격과 비교
            for (int j=1; j<=i; j++) { // 바텀탑 방식
                int tmp = dp[j] + dp[i-j];
                if (tmp > max) { max = tmp; }
            }
            dp[i] = max;
        }

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

 

로그인

 

 

작성일자: 2023-11-26