2022/04/12) 9. 동전교환 [재귀함수와 완전탐색(DFS:깊이우선탐색)]

1. 문제

<동전교환>
: 다음과 같이 여러 단위의 동전들이 주어져 있을 때, 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.
거슬러 줄 동전의 최소개수를 출력한다.
(첫 번째 줄에는 동전의 종류개수 N이 주어지고, 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음에 거슬러 줄 금액 M이 주어진다.)

2. 해결 방법

1. 이전에 했던 거 처럼 포함/불포함의 여부가 아니라, 중복순열 느낌으로 짜야한다. 그 이유는 1/3/5라는 동전이 여러 번 쓰일 수도 있기 때문이다. (위에처럼 하면 이렇게 구현못함)
   그리하여 L의 값(=동전개수)을 구하는 게 핵심이다!
2. 더이상 생각하면 화병날 거 같아서 낼 추가로 다시 수정하겠다.

3. 정답

        <script>
            function solution(m, arr){
                let answer = Number.MAX_SAFE_INTEGER;
                let n = arr.length;
                function DFS(L, sum){
                    if(sum > m) return; //합이 15넘어가서 멈추는 조건(if)에 들어가지 않고, 계속 뻗어갈 수(else)도 있으므로
                    if(L>=answer) return; //answer(최소동전개수)보다 같거나 더 클 경우엔 굳이 할 필요없음. 가지치기해버리기
                    if(sum === m){ //멈추는 조건
                        answer = Math.min(answer, L);
                    }else{
                        for(let i = 0; i < n; i ++){ //arr배열
                            DFS(L+1, sum+arr[i]);
                        }
                    }
                }
                DFS(0,0);
                return answer;
            }
            let arr=[1, 2, 5];
            console.log(solution(15, arr));
        </script>

4. 내 코드와 비교 그리고 반성

아 진짜 돌머린가.. 중복순열이 이해가 잘 안간다. 중복순열 복습하는데 이해가 안가서 스택을 여러번 그렸던 거 같다.(1시간 넘게 쳐다본 듯) 이건 이제 좀 이해가 가는데, 이 문제는 또 이해가... 하ㅠㅠ 뭔가 왜캐 헷갈리지.. 잠깐 한시간동안만 보려 했는데 앞에 문제까지 보는 바람에 3시간은 본 듯하다. 그리고 난 처음에 cnt변수를 선언해서 했었다. 근데 결국 L(Level)이 동전개수였꾼! 하하하. 낼 다시 봐야겠다. 화가 되겠다.