[Ch.08 - DFS] 07. 동전교환 #

5. 동전교환

-> 냅색 알고리즘으로 풀기

https://and-some.tistory.com/662

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

 

 

설명

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

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

입력

첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고,

그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.각 동전의 종류는 100원을 넘지 않는다.

출력

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

예시 입력 1 

3
1 2 5
15

예시 출력 1

3

---

동전 교환의 경우

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

 

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

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

 

 

문제 풀이 순서

1. 동전의 종류 개수를 크기로 하는 배열 선언 -> 정렬을 해야하기 때문에, 배열을 Integer로 선언
   
   • static Integer[] arr;
   • arr = Integer [n];
2. 배열 내림차순으로 정렬 [큰 금액부터해야 시간을 단축시킬 수 있다.]
3. 동전의 종류 개수 N -> N개의 종류 -> 거슬러 줄 금액 M
4. 사용된 동전의 개수, 금액의 합을 파라미터로 한 DFS
   1. 동전 개수가 최솟값보다 클경우 -> false
   2. 합이 거슬러줄 금액보다 큰 경우 -> false
   3. 합이 거슬러줄 금액이 될 경우
      1. 가장 작은 값을 answer에 저장
   4. 그 외의 경우에는, 동전의 종류 개수만큼 반복
      • 동전의 개수를 하나 늘리고, SUM에 배열의 i번째를 넣고, arr를 다시 만든다.
        -> DFS(L+1, sum+arr[i], arr);
        
        

#타임 리밋 방지

if(L>=answer) {
		//answer보다 큰 L에서는 리턴
			return;
		}

---

 

import java.util.Arrays;
import java.util.Collections;
//동전교환
//동전의 종류 개수 N
//N개의 종류
//M은 거스름돈 총합
//최소의 동전 개수
import java.util.Scanner;
//동전 교환
//동전 종류 개수 N
//N개의 동전의 종류
//거슬러 줄 동전 수 M
//거슬러 줄 동전의 최소개수
class Main {
	static int n, m, answer= Integer.MAX_VALUE;
	public void DFS(int L, int sum, Integer[] arr) {
		//L : 동전의 개수
		//sum : 동전의 총합
		//arr : 체크 배열
		if(sum>m) {
		//총합이 m보다 클경우 리턴
			return;
		}
		if(L>=answer) {
		//answer보다 큰 L에서는 리턴
			return;
		}		
		if(sum==m) {
		//총합이 m이 되었을 ��
			answer=Math.min(answer, L);
			//L의 개수 중에 가장 작은 값을 answer로 설정 -> L이 기존 값보다 작으면 변경
		}
		else {
		//그 외의 경우
			for(int i=0;i<n;i++) {
				//동전의 종류만큼 반복
				DFS(L+1, sum+arr[i], arr);
				//동전의 개수를 하나 늘리고, SUM에 배열의 i번째를 넣고, arr를 다시 만든다.
			}
			
		}
	}
	public static void main(String[] args) {
		Main T =new Main();
		Scanner kb=new Scanner(System.in);
		n=kb.nextInt();
//		int [] arr= new int[n];
//		//기본형 배열
		Integer[] arr = new Integer[n];
		//객체형 배열
		for(int i=0;i<n;i++) {
			arr[i]=kb.nextInt();
		}
		Arrays.sort(arr, Collections.reverseOrder());
		//작은 금액부터가 아닌 큰 금액부터 적용해야 시간 복잡도가 줄어든다.
		//-> 내림차순으로 정렬
		//sort를 사용하려면 기본형 배열이 아니라 객체형 인트로 변환
//		for(int x: arr) {
//			System.out.print(x+" ");
//		}
//		내림차순 정렬 확인
			m=kb.nextInt();
			T.DFS(0, 0, arr);
			System.out.println(answer);
		}
}

 

 

 

1. DFS(L, sum) : L: 동전 개수, sum : 총합

2. 중단 조건 설정 : sum==m, L>=answer, sum>m

3. answer = Math.min(answer, L)

4. 거스름돈을 줄 동전의 크기가 큰 순부터 확인

-> Wrapper Class : Integer [] arr = new Integer[n];

-> Arrays.sort(arr, Collections.reverseOrder());

import java.util.*;
  
public class Main {
  static int n,m;
  static int answer=Integer.MAX_VALUE;

  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    n = in.nextInt();
    Integer[] arr =new Integer[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
    m=in.nextInt();
    Arrays.sort(arr,Collections.reverseOrder());
    solution(0,0,arr);
    System.out.println(answer);
  }
  static void solution(int L,int sum, Integer[] arr){
    if(sum>m||L>=answer){
      return; 
    }
    if(sum==m){
      answer=Math.min(answer, L);
    }
    else{
    for(int i=0;i<n;i++){
    solution(L+1, sum+arr[i], arr);
    }
    }
  }
}

 

 

 

 

 

냅색 알고리즘

(1) 거스름돈 값을 배열의 길이로하는 dy 배열 : dy[i]는 i라는 거스름돈을 줄 수 있는 최소 동전 개수

(2) dy배열은 0을 제외하고, 모두 최댓값으로 초기화 한다.

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int[] 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,arr));
  }
  static int solution(int n,int m, int[]arr){
    //dy[i] : i라는 거스름돈을 줄 수 있는 최소 동전의 개수
    int[] dy = new int[m+1];
    //가장 큰 값으로 초기화
    Arrays.fill(dy, Integer.MAX_VALUE);
    //0이라는 거스름돈의 최소 동전 개수는 0개 이므로
    dy[0]=0;
    //가장 작은 동전부터 시작
    Arrays.sort(arr);
    for(int i=0;i<n;i++){
      //해당 동전 값
      int pt= arr[i];
      for(int j=pt;j<m+1; j++){
        //해당 동전으로 줄 수 있는 최소 동전 개수에 하나 추가한 값이 더 작을 경우 작은 값 선택
        dy[j]=Math.min(dy[j], dy[j-pt]+1);
        //dy[j-pt] : 해당 동전 값을 제외한, 거스름돈을 줄 수 있는 최소 동전 개수
        //즉, 냅색 알고리즘은 항상 최소 값을 배열에 저장하는데,
        //원하는 값으로 하는 길이에 해당하는 배열이므로, 배열의 마지막 값이 결과값
      }
    }
    return dy[m];
  }
}