동전교환 (DFS)

최준호·2021년 10월 1일
0

알고리즘 강의

목록 보기
65/79

문제

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

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

  • 제한사항

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

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

코드

public class ExchangeOfCoins {
    static int n,m=0;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] coins = new int[n];
        for(int i=0; i<n; i++){
            coins[i] = sc.nextInt();
        }
        m = sc.nextInt();

        dfs(0, 0, coins);

        System.out.println(min);
    }
    public static void dfs(int level, int sum, int[] coins){
        if(level>=min) return;
        if(sum>m) return;
        if(sum == m){
            min = Math.min(min, level);
        }else{
            for(int i=n-1; i>=0; i--){
                dfs(level+1, sum+coins[i], coins);
            }
        }
    }
}

설명

저번 시간에 공부한

중복 순열 출력하기 (DFS)

의 개념을 모두 이해했다면 쉽게 풀수 있을 수도 있는 문제다. 왜 쉽게 풀수 있을 수도 있냐면... 시간복잡도가 계속 터지기 때문이다...ㅜㅜ

먼저 내가 처음 풀이했던 코드는

public class ExchangeOfCoins {
    static int n,m=0;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] coins = new int[n];
        for(int i=0; i<n; i++){
            coins[i] = sc.nextInt();
        }
        m = sc.nextInt();

        dfs(0, 0, coins);

        System.out.println(min);
    }
    public static void dfs(int level, int sum, int[] coins){
        if(sum>m) return;
        if(sum == m){
            min = Math.min(min, level);
        }else{
            for(int i=0; i<n; i--){
                dfs(level+1, sum+coins[i], coins);
            }
        }
    }
}

과 같았다. 위의 코드와 차이점이 뭔지 아직 모를 수 있는데 이제 하나씩 살펴보자.

우선 코드를 작성할때 백트레킹 조건으로 동전의 합이 우리의 목표 값인 m보다 크다면 모두 return 해주어 더이상 검사하지 않았다. 이 조건만 붙여서 실행하니 2번 테스트까지는 모두 정상적으로 통과했는데 나머지 문제에서 timeout이 났다. 그럼 이제 우리는 시간복잡도를 봐봐야하는데...

위의 제한사항을 보면 n은 12까지 들어온다고 적혀있고 m은 500까지 들어온다. 그럼 12^500는 몇일까?

인터넷에 검색하여 계산해보니
3.6360291795869936842e+238

이렇게만 봐도 벌써 시간 복잡도가 터지고 있다... 그래서 우리는 백트레킹 조건을 추가해줘야 하는데 내 결론은

if(level>=min) return;

이 코드를 추가하는 것이였다. level이 이미 최소값보다 크다면 우리는 더 이상 코드를 진행시킬 필요가 있을까? 아니다 우리는 최소값만 구해내면 되기 때문에 더이상 코드를 진행 시킬 필요가 없다.

그렇게 코드를 또 돌려보면 또 타임아웃이 난다. 그 이유는 더 최적화를 해보라는 것인데. 여기서 나는 돈을 거슬러줄 때 우리가 1원짜리부터 계산해보지 않지 않을까? 라는 생각으로 큰돈 부터 계산해서 내려와보자로 계획을 바꿨다. 그렇게되면 배열을 거꾸로 하기 위해

for(int i=0; i<n; i--){
	dfs(level+1, sum+coins[i], coins);
}

배열을 역순으로 출력하도록 하였는데... 강사님은 이 부분을 수정하시지 않고 main에서 배열을 받았을 때

Arrays(coins, Collections.reversOrder());

코드를 통해 해결하시더라 ㅜㅜ 이 방법이 훨씬 맞는거 같다. 그래도 내가 통과한 코드라 위의 코드로 적어놓겠다...!

dfs의 이진트리 구조가 아닌 여러 갈래로 뻗어나가는 문제를 해결해봄!
그리고 dfs를 구현하며 최적화 작업을 진행해볼 수 있는 문제라 흥미롭고 재미있게 풀수 있었음!

출처

profile
코딩을 깔끔하게 하고 싶어하는 초보 개발자 (편하게 글을 쓰기위해 반말체를 사용하고 있습니다! 양해 부탁드려요!) 현재 KakaoVX 근무중입니다!

0개의 댓글