<문제> 효율적인 화폐 구성 (Dynamic Programming)

 

문제 3. 효율적인 화폐 구성

 

 

 

 

 

 

---

 

문제 풀이 방식

 

 

 

다음과 같이 점화식을 만들 수 있다.

 

 

 

화폐는 10,000 이하인 값이므로 각 인덱스는 10,001 값으로 초기화 해준다.

 

 

 

 

화폐의 단위가 2일 때를 살펴보면

 

 

인덱스 2의 값은 2 하나로, 4는 2 두 개로, 6은 2 세 개로 만들 수 있다.

 

 

 

 

 

화폐의 단위가 3일 때를 살펴보면

 

 

인덱스 3의 값은 3 하나로, 6은 3 두 개로 표현할 수 있다.

 

 

여기서 인덱스 5와 7도 만들 수 있다.

 

 

인덱스 5에서 3칸 앞을 살펴보면 2가 있으므로 2의 값에 3을 더하면 5라서 인덱스 2의 값인 1 + 1을 해줘 2가 됨

 

 

인덱스 7도 3칸 앞을 살펴보면 인덱스 2를 두 개 활용한 4가 있음. 인덱스 4 값인 2 + 1 해줘서 3이 됨

 

 

 

 

화폐의 단위가 5일 때를 살펴보면

 

인덱스 5는 1로 갱신되며

 

인덱스 7 또한 인덱스 2의 값인 1 에 1을 더한 2의 값으로 갱신될 수 있다.

 

 

 

 

 

 

그러니까 화폐 단위를 하나씩 넣어 값을 min 값으로 갱신해주면 된다.

 

 

 

 

 

코드

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


public class efficientMoney { // 효율적인 화폐 구성 DP
	
	public static void main(String[] args) throws IOException{
		int money[];
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		money = new int[N];
		int d[] = new int[M + 1];
		Arrays.fill(d, 10001);
		
		d[0] = 0;
		
		for(int i = 0; i < N; i++) 
			money[i] = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < N; i++) 
			for(int j = money[i]; j <= M; j++) 
				if(d[j - money[i]] != 10001)
					d[j] = Math.min(d[j], d[j - money[i]] + 1);


		if(d[M] == 10001) System.out.println(-1);
		else {
			System.out.println(d[M]);
		}
		
	}

}

 

 

 

 

 

 

 

출처 : https://www.youtube.com/watch?v=5Lu34WIx2Us&t=1495s