백준 - 2295

문제

입력/출력

풀이

참고 문제 통증(2)

참고 통증(2) 해설지

dp[n]에 n의 값을 만들 수 있는 동전의 최솟값을 저장합니다.
0의 값을 만드는 데 동전이 0개 필요하기때문에 dp[0]= 0으로 초기화 해주고,
나머지 인덱스에는 k의 최대값보다 큰 수로 초기화합니다.
(최소 개수를 찾을 때는 큰 수로 초기화,최대 개수를 찾을 때는 작은 수로 초기화)

i번째 dp는
dp[i],dp[i-동전의 값]+1 두 값중에 최소값이 있다는 규칙을 찾을 수 있고,
dp[i] = Math.min(dp[i],dp[i-n]+1) //동전 값 n 으로 구할 수 있습니다.

코드

import java.util.*;
import java.io.*;
class Main{
    static int n; //동전의 수
    static int k; // 목표 값
    static int[] coins; // 주어진 동전의 값
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        coins = new int[n+1];
        for(int i=1;i<=n;i++){
            st =new StringTokenizer(br.readLine());
            coins[i]=Integer.parseInt(st.nextToken());
        } // 입력
        // Arrays.sort(coins);
        // 작은 값부터 차례대로 비교 (필수x)
        int[] dp = new int[k+1]; // 목표 값에 필요한 동전 개수를 저장할 dp
        dp[0] = 0; //0 값은 동전 0개가 필요하다
        for(int i=1;i<=k;i++){
            dp[i]=10001; //k의 최대값보다 큰 수로 초기화
        }
        for(int i=0;i<=n;i++){ 동전 수 만큼 반복
            for(int j=coins[i];j<=k;j++){
                dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
                //초기에 1의 동전 값으로 필요한 동전 개수와 k의 최대값과 비교하면 j의 값이 dp[j]에 저장됨 
            }
        }
        if(dp[k] == 10001){ // 찾은 규칙으로 구할 수 없을 때
            System.out.println(-1); -1 출력
        }else{
            System.out.println(dp[k]); // 목표 값의 dp 값 출력
        }
    }
}