백준 11052 카드 구매하기 자바(java)

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

11052번: 카드 구매하기

 

풀이 방법

다이나믹 프로그래밍을 사용하여 풀었다.

dp 문제를 풀 땐 먼저 구하고자 하는 것이 무엇인지를 생각하는 것이 가장 쉬운 접근 방법인 것 같다.

구하고자 하는 것이 N개 카드 구매 시 지불할 금액의 최댓값이 이므로 DP 배열의 값을 각 구매 개수에 따른 지불 최댓값을 저장해야겠다고 생각했다. 즉, 카드 2개 구매 시 최댓값이 10이면 dp[2] = 10이 되는 것이다.

 

카드 구매 시 i번 카드팩을 포함하는 경우와 포함하지 않는 경우 두 가지로 나누어 최댓값을 비교해주면

점화식은 총 j개의 카드를 구매한 경우 dp[j] = max(dp[j-i] + p[i], dp[j])가 된다. (단, i <= j <= N)

따라서, 1~N의 모든 카드팩에 대해 i번 카드팩을 구매했을 때 가능한 모든 구매 개수에 대해 dp 점화식을 사용하여 dp 값을 갱신해주면 된다.

 

 

코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N+1];
        int[] P = new int[N+1];

        // 카드팩 입력
        String[] line = br.readLine().split(" ");
        for(int i=1; i<=N; i++) {
            P[i] = Integer.parseInt(line[i-1]);
        }

        for(int i=1; i<=N; i++) {
            for(int j=i; j<=N; j++) {
                dp[j] = Math.max(dp[j-i] + P[i], dp[j]);
            }
        }
        System.out.println(dp[N]);
    }
}