[059] 11052. 카드 구매하기

✨ 알고리즘 분류 : 다이나믹 프로그래밍

 

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

11052번: 카드 구매하기

 

 

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- 구매하고자 하는 양에 맞는 금액의 최댓값을 구하기

- 카드팩 n개는 1씩 오름형태

- 적거나 넘치면 안 됨

 

 

 

🧶 풀이과정 

 

최댓값을 구하는 건 또 오랜만이라 잠깐 헤메는 시간을 가졌다.

결국, 최솟값과 같이 전까지의 결과물과 비교하여 높은 것을 넣으면 되는데, min이 아니라 max값을 담는 것과 같다고 생각하면 된다.

 

그러니까

카드 한개를 구매할 때는 무조건 팩의 첫번째 것을 가져가고

카드 두개를 구매할 때는 두개짜리 한팩 / 한개로 저장되어있는 값 + 팩의 첫번째

카드 세개를 구매할 때는 세개짜리 한팩 / 한개로 저장되어 있는 값 + 팩의 두번째 / 두개로 저장되어 있는 값 + 팩의 첫번재

카드 네개를 구매할 때는 네개짜리 한팩 / 한개로 저장되어 있는 값 + 팩의 세번째 / 두개로 저장되어 있는 값 + 팩의 두번째 / 세개로 저장되어 있는 값 + 팩의 첫번째

 

이런 식으로 진행된다고 볼 수 있다.

이걸 공식으로 생각해보면

dp[i] = Math.max(dp[i], dp[i-j] + pack[j])

 

라고 정의할 수 있을 것이다.

이것을 토대로 코드를 짜면

 

 

 

🏹 제출코드

 

package data_structure_part_01;

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

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

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] pack = new int[n+1];
        int[] dp = new int[n+1];

        // 팩에 값 담고
        for(int i = 1; i <= n; i++){
            int price = Integer.parseInt(st.nextToken());
            pack[i] = price;

            // dp 굴리기
            // 최대값 구해오기
            for(int j = 1; j <= i ; j++){

                dp[i] = Math.max(dp[i], dp[i-j] + pack[j]);

            }
        }

        System.out.println(dp[n]);

        br.close();

    }
}