[2294] 동전 2 - Java[자바]

 

 

| 문제 링크

 

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

2294번: 동전 2

 

 

 

 

---

 

 

 

 

| 문제

 

1. N개의 종류의 동전을 활용해 동전들의 합이 K가 되는 최소한의 동전 갯수를 출력하시오.
   동전의 합으로 K를 만들 수 없다면 -1을 출력

 

 

 

 

---

 

 

 

| 풀이

 

1. 길이가 K+1인 배열을 생성합니다.
2. i번째 배열의 값에 대해 동전을 하나씩 값을  탐색합니다. 동전의 크기보다 인덱스가 큰 경우에는 동전의 크기 만큼 전의 인덱스 값(해당 인덱스에는 해당 값을 구성한 동전의 최소 개수가 입력되어 있음)에 +1을 입력해 줍니다.
3. 2번에서 구한 인덱스 별 각각의 동전의 개수 중 최소 값을 해당 인덱스 값으로 설정합니다.

 

 

 

---

 

 

 

 

| 코드

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int[] tokens = new int[n+1];
		int[] dp = new int[m+1];
		
		for(int i = 1; i<=n; i++) {
			tokens[i] = Integer.parseInt(br.readLine());
		}
		
		for(int i = 1; i<=m; i++) {
			int min = Integer.MAX_VALUE-1;
			for(int j = 1; j<=n; j++) {
				if(i>=tokens[j]) {
                    min = Math.min(min,dp[i-tokens[j]]+1);
				}
			}
			dp[i] = min;
		}
		
		if(dp[m]<Integer.MAX_VALUE-1)
			bw.write(String.valueOf(dp[m]));
		else
			bw.write("-1");
		br.close();
		bw.close();
	}

}