[JAVA] 백준 2294번 : 동전 2

 

---

 

• 생각

[JAVA] 백준 2293번 : 동전 1

[JAVA] 백준 2293번 : 동전 1

위 문제랑 비슷하지만 다르다.

다른점은 동전 1에서는 S 원을 만들 수 있는 모든 경우의 수를 구하지만,

동전 2에서는 최소한의 동전을 사용해서 만들 때 사용한 동전의 개수를 구하는 문제이다.

 

잘 생각이 안나서 찾아보니 점화식음 다음과 같다.

dp[j] = Math.min(dp[j], dp[j-coin[i]]+1);

 

 

1. 사용한 동전의 개수가 최악일 경우 100,000개이기 때문에 10001로 초기화 한다.

 

2. 점화식의 구조를 따르기 위해 dp[0] = 0으로 초기화한다.

 

3. dp[S] = 100001이면 해당 금액을 만들 수 없다는 의미이므로 -1을 출력한다.

 

• 코드

정답 코드 : 점화식을 통해 구현했다.

 

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

public class Main {
	static int N, S, value;
	static int[] coin, dp;

	public static void main(String[] args) throws Exception {
		SetData();
		dp();
		System.out.println(value);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());

		coin = new int[101]; // 인덱스 번호 1부터 +1씩 해서 배열 선언
		dp = new int[10001];

		for (int i = 1; i <= N; i++)
			coin[i] = Integer.parseInt(br.readLine());

		Arrays.fill(dp, 10001);
		dp[0] = 0;
	}

	private static void dp() {
		// i는 x번째->coin[x번째 동전 종류]의 경우를 의미
		// j는 i의 동전 종류로 1~s원를 채우는 경우의 수를 의미
		for (int i = 1; i <= N; i++) {
			for (int j = coin[i]; j <= S; j++) {
				dp[j] = Math.min(dp[j], dp[j-coin[i]]+1);
			}
		}
		
		if(dp[S] == 10001)
			value = -1;
		else
			value = dp[S];
	}
}