인프런 동전교환 DFS

박은빈·2022년 12월 16일

코딩

목록 보기

18/19

동전의 종류의 개수 n이 주어진다.
그리고 그 동전의 종류만큼 동전이 주어지고 거슬러 줄 금액 m이 주어진다
동전의 종류들을 더해서 m을 만드는데 최소동전의 개수를 구해야한다

만약 1, 2, 5의 동전이 주어지고 거슬러야되야 되는 돈 m이 15라면
5+5+5 = 15로 정답은 3이다

풀이과정

중복이 가능하므로 중복순열을 이용한다
코인들을 배열로 만들어놓고 for문을 이용해 코인들을 순회한다
여기서 코인의 개수 cnt를 더하면서 합계 sum에 코인들을 더한다
for문이 0번째일때 dfs(cnt+1, sum+coins[0])을 선언하면 다시 해당 dfs의 함수 안으로 들어오게되고 그 안에서 다시 dfs(cnt+1, sum+coins[0])을 선언하게 될 것이다.
그리고 제일 앞에 만약 주어진 합계 m과 sum이 같다면 static으로 선언된 total과 cnt중에 작은 값은 total에 넣는다.
total의 기본값은 500을 주었는데 계산해본결과 cnt의 최대값이 500이기때문이다 이유는 코인의 최소값이 1이고 거스름돈의 최대값이 500이기때문이다
그리고 최소값을 구하기때문에 total보다 cnt가 크면 의미가 없기 때문에 해당 if문에 걸릴경우 바로 return을 해주었다
또 sum이 m보다 큰 경우에도 의미가 없기때문에 return을 해주었다
마지막으로 최소값을 구하기 위해서는 큰 수부터 더해보는것이 구하기가 빠르다. 그렇기때문에 코인의 종류를 받은 배열을 내림차순으로 정렬시킨다

코드

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

public class Inf8_5ExchangeCoin {
    private static int n, m, total = 500;
    private static Integer[] coins;

    private static void dfs(int cnt, int sum) {
        if(total <= cnt) return;
        if(sum > m) return;
        if(sum == m) {
            total = Math.min(total,cnt);
        } else {
            for(int i=0; i<n; i++) {
                dfs(cnt+1, sum+coins[i]);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        coins = new Integer[n];

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

        Arrays.sort(coins, Collections.reverseOrder());


        m = sc.nextInt();

        dfs(0,0);

        System.out.println(total);

    }
}