[이것이 취업을 위한 코딩테스트다] Ch08. 다이나믹 프로그래밍 - 효율적인 화폐 구성 (Java)

문제

N가지 종류의 화폐가 있다.

화폐의 개수를 최소한으로 이용해 그 가치의 합이 N원이 되도록 하려고 한다.

각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.

예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

1<=N<=100

1<=M<=10000

(예시 입력)

2 15

2

3

(예시 출력)

5

 

(예시 입력)

3 4

3

5

7

(예시 출력)

-1

풀이/후기

거스름돈 문제와 유사하지만, 화폐의 단위가 배수 관계가 아니라서 그리디 알고리즘으론 풀 수 없음

이럴 때 다이나믹 프로그래밍을 사용함

일단 만들고자 하는 금액 + 1 만큼의 배열을 선언해서 값을 모두 10001으로 초기화 함

배열의 인덱스가 만들고자 하는 금액임

화폐 단위 별로 반복문을 돌려서 인덱스를 화폐 단위로 만들 수 있다면 배열의 값을 변경함

코드

package ThisIsCT;

import java.io.*;
import java.util.*;

public class ch08_05 {
	// Ch.08 다이나믹 프로그래밍 Dynamic Programming DP
	// 효율적인 화폐 구성
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(str.nextToken());
		int M = Integer.parseInt(str.nextToken());

		int[] arr = new int[N+1];		//화폐의 단위 저장 배열
		int[] R = new int[M+1];
		
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		//M의 최대값 10000보다 1이 큰 수(절대 나올 수 없는 수로 초기화)
		Arrays.fill(R, 100001);
		/*
		for (int i=0; i<M+1; i++) {
			R[i] = 100001;		
		}
		*/
		
		R[0] = 0;
		for (int i=0; i<N; i++) {
			//사용할 화폐의 단위 선택
			int temp = arr[i];
			
			for (int j=temp; j<M+1; j++) {
				//j : 나타내고자 하는 금액
				if (R[j-temp] != 100001) {
					R[j] = Math.min(R[j], R[j-temp] + 1);
				}
			}
		}
		
		if (R[M] == 100001) {
			System.out.println(-1);
		} else {
			System.out.println(R[M]);
		}
		
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/41e0e6c7fd6de7a5995d91012819cae0fb699d8a

참고

https://youtu.be/5Lu34WIx2Us?t=2608