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

문제를 요약하면

n개의 카드를 제일 비싼 값을 주고 사고싶다는 미친 문제

1~n개가 들어있는 팩이 각각 가격이 다르다.

 

예를 들어 3개의 카드를 살 때

경우의 수 

1. 1개팩 3개

2. 1개팩 1개 2개팩 1개

3. 3개팩 1개

중 제일 비싼값을 return 해주면 된다.

 

경우의 수를 식으로 표현하면

maxPrice[3] = max(maxPrice[3], + maxPrice[2] + price[1], + maxPrice[1] + price[2])

 

3개 팩의 max값을 구하기 위해

1개, 2개를 구매햇을 때의 max값을 알아야 하기 때문에 for문으로 1부터 입력값 n 까지 루프를 돌린다.

 

식으로 표현하면

maxPrice[i] = max(maxPrice[i], maxPrice[i-j] + price[j]);

 

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(reader.readLine());
        String[] tempPrice = reader.readLine().split(" ");
        int[] prices = new int[cnt+1];
        int[] maxPrice = new int[cnt+1];
        for(int i=0; i< tempPrice.length; i++){
            prices[i+1] = Integer.parseInt(tempPrice[i]);
        }

        for(int i = 1 ; i<prices.length; i++){
            for(int j = 1; j<=i; j++){
                maxPrice[i] = Math.max(maxPrice[i], maxPrice[i-j]+prices[j]);
            }
        }
        System.out.println(maxPrice[cnt]);
        reader.close();
    }
}