[060] 16194. 카드 구매하기 2

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

 

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

16194번: 카드 구매하기 2

 

---

 

 

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

 

- 카드를 사기 위해 지불해야 하는 금액 중 제일 적은 값 출력

- 카드 개수의 합 = n

 

 

 

🧶 풀이과정 

 

저번에 최대값을 구하는 것의 반대로, 최솟값을 구하는 것이다.

 

2024.04.16 - [Algorithm] - [059] 11052. 카드 구매하기

[059] 11052. 카드 구매하기

 

여기에서 조금 다른 점은, Max가 아니라 Min을 통해 최솟값을 구한다는 점과

처음 최솟값을 구하기 위해서 미리 dp[i]에 값을 대입해야 한다는 것이다.

비교하기 위한 값 중에 일정한 값은 무엇이 있을까? 그건 pack[i]이기 때문에 초기 값을 설정하고, min으로 비교를 수행하며 넣는 것으로 한다.

 

 

 

🏹 제출코드

 

package data_structure_part_01;

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

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

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

        int[] pack = new int[n+1];
        int[] dp = new int[n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 1; i <= n ; i++){

            int card = Integer.parseInt(st.nextToken());
            pack[i] = card;
            dp[i] = pack[i];

            for(int j = 1; j <= i ; j++){

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

        }

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

        br.close();
    }
}