[Ch.10 - DP] 05. 동전교환 [+냅색 알고리즘]

5. 동전교환(냅색 알고리즘)

 

냅색 알고리즘 

: 담을 수 있는 무게가 정해진 백팩에 가장 비싼 금액의 물건으로 채우는 알고리즘

 

설명

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?

각 단위의 동전은 무한정 쓸 수 있다.

입력

첫 번째 줄에는 동전의 종류개수 N(1<=N<=50)이 주어진다.

두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.

각 동전의 종류는 100원을 넘지 않는다.

출력

첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

예시 입력 1 

3
1 2 5
15

예시 출력 1

3

---

동전 교환의 경우

: DFS와 DP 두 가지 방법으로 풀이할 수 있다.

 

DFS는 동전의 개수가 많으면 타임리밋이 걸릴 확률이 높다.

-> DP를 이용해 최소개수를 찾는다.

 

문제 풀이 순서

1. dy라는 거슬러줄 금액을 배열의 개수로 하는 배열을 선언한다.
2. dy[0]을 제외하고, Integer.MAX_VALUE로 초기화한다.
3. dy[i]는 i라는 금액을 만드는데 필요한 최소 동전의 개수로
   arr를 돌면서 기존갑과 비교해 더 적은 동전 개수가 가능하면 변경한다.
4. 이중for문을 돌면서 j는 동전의 금액부터 시작해, 배열의 길이만큼 돈다.
   dy[j]=dy[j-arr[i]]+1로, 기존 값과 비교해 더 작은 값을 택한다.

---

import java.util.*;
  
public class Main {
  static int[] arr;
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    arr=new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
    int m = in.nextInt();
    System.out.println(solution(n,m));
  }
  static int solution(int n, int m){
    int answer=0;
    int[] dy = new int [m+1];
    dy[0]=0;
    
    for(int i=1; i<m+1;i++){
      dy[i]=Integer.MAX_VALUE;
    }

    for(int i=0;i<n;i++){
      //arr = 1,2,5
          for(int j=arr[i];j<m+1;j++){
      	if(dy[j]>dy[j-arr[i]]+1) dy[j]=dy[j-arr[i]]+1;
        }
    }
    
    return answer=dy[m];
  }
}

 

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	static int m, answer;
	static int[] arr, dy;

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();
		m = kb.nextInt();
		dy = new int[m + 1];
		solution(arr);
		System.out.println(dy[m]);
	}

	static void solution(int[] arr) {

		for (int i = 0; i < m+1; i++) {
			dy[i] = Integer.MAX_VALUE;
		}
		dy[0] = 0;
		for (int i = 0; i < arr.length; i++) {
			for (int j = arr[i]; j < m + 1; j++) {
				//dy[j] = dy[j - arr[i]] + 1;
				dy[j] =Math.min(dy[j], dy[j - arr[i]] + 1); 
			}
		}

	}
}

 

 

+) 세련된 풀이

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int m, answer;
	static int[] arr, dy;

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();
		m = kb.nextInt();
		dy = new int[m + 1];
		System.out.println(solution(arr));
		
	}

	static int solution(int[] arr) {
		Arrays.fill(arr, Integer.MAX_VALUE);
		dy[0] = 0;
		for (int i = 0; i < arr.length; i++) {
			for (int j = arr[i]; j < m + 1; j++) {
				//dy[j] = dy[j - arr[i]] + 1;
				dy[j] =Math.min(dy[j], dy[j - arr[i]] + 1); 
			}
		}
		return dy[m];

	}
}

 

Arrays.fill(arr, Integer.MAX_VALUE);

-> Arrays.fill 메서드를 이용하면, 배열을 원하는대로 초기화할 수 있다.