[Baekjoon] 2294_동전 2

문제(출처: https://www.acmicpc.net/problem/2294)

---

< 동전 2 >

 

문제 풀이 

 

주어진 예시와 같이 동전이 [1, 5, 12] 있고, 15를 만든다고 가정하자.

 

1일 때 1 동전 1개

2일 때 1 동전 2개

          ...

5일 때 1 동전 5개, 5 동전 1개 -> 5 동전 1개

이런 식으로 구하면 아래와 같이 구해진다.

 

 

 

my solution (Java)

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

public class _2294_ { // 동전 2

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		int arr[] = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(bf.readLine());
		}

		int dp[] = new int[k + 1];
		for (int i = 1; i < k + 1; i++) {
			dp[i] = Integer.MAX_VALUE;
		}

		for (int i = 1; i < k + 1; i++) {
			for (int j = 0; j < n; j++) {
				if (i - arr[j] < 0 || dp[i - arr[j]] == Integer.MAX_VALUE) {
					continue;
				}
				dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
			}
		}

		if (dp[k] == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(dp[k]);
		}
	}
}

변수)
n, k : 동전 종류 개수, 합
arr : 동전 가치 
dp : 사용한 동전의 개수 

 

동전 종류 개수와 합을 입력받는다. 동전 종류 개수만큼 동전의 가치를 입력받아 arr에 저장한다. 1부터 k원까지 탐색하며 (현재 가치 - 동전 값)이 0보다 작거나 그 값을 만들 수 없었던 경우를 제외하고 사용한 동전의 개수를 최솟값으로 업데이트한다. 

 

최종 dp [k] 값이 Integer.MAX_VALUE인 경우는 불가능한 경우이므로 -1을 출력하고, 그렇지 않은 경우는 dp [k] 값을 출력한다. 

---

---