Java : 동전 교환(냅색 알고리즘)

문제

풀이

• 완전탐색 dfs 로 풀리던 문제를 시간 복잡도를 고려하여 냅색으로 풀어본다.

• coin 배열 coinArr과 동전 개수를 저장할 dp 배열 dy를 만든다.

• j번째 동전의 개수 인 dy[j]는 j원을 거슬러 주기 위해 사용된 동전의 최소 개수 이다.

• coin 별로 거슬러 줄 동전의 개수를 계산하고 dy에 저장해준다.

잡담

• dp 알고리즘의 일종으로 냅색은 배낭과 보석이 있을 때 한정된 공간(가방의 크기)에 최대 가치의 보석을 담으라는 의미에서 지어졌다고 한다.(knapsack=배낭)

전체 코드

package inflearn;

import java.util.Scanner;

public class I1005 {

	static int n;
	static int m;
	static int[] dy;
	static int[] coinArr;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		coinArr = new int[n];

		for (int i = 0; i < n; i++) {
			coinArr[i] = sc.nextInt();
		}

		m = sc.nextInt();
		dy = new int[m + 1];
		for (int i = 1; i < dy.length; i++) {
			dy[i] = Integer.MAX_VALUE;
		}

		System.out.println(knapsack());
	}

	static int knapsack() {
		for (int coin : coinArr) {
			for (int j = coin; j <= m; j++) {
				int tmp = dy[j - coin] + 1;
				if (dy[j] > tmp) dy[j] = tmp;
			}
		}
		return dy[m];
	}
}