문제링크

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

구현방법

이전 카드 구매하기와 같은 문제로 이번엔 최솟값을 구하는 문제이다.

그렇기 때문에 기본적인 로직은 카드 구매하기와 같지만 dp의 값을 99999로 채워주고 dp[0] 값만 0으로 만든뒤에

앞서 카드구매하기 로직에서 Math.max 를 Math.min 으로 바꿔서 구하면 되는 문제.

알고리즘

• 다이나믹 프로그래밍

CODE

import java.io.*;
import java.util.*;


public class Main {
    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[] CardValue = new int[N+1];

        int[] dp = new int[N+1];
        
        //각 개수별 가격 결정
        for(int idx = 1; idx <=N;idx++){
            CardValue[idx] = Integer.parseInt(st.nextToken());

        }


        Arrays.fill(dp,99999);
        dp[0]= 0;
        for(int index = 1; index <=N;index++){
            for(int j = 1; j<=index;j++){
                dp[index] = Math.min(dp[index],dp[index-j] + CardValue[j]);
            }
        }

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


    }
}