2022/04/27) 15. 수들의 조합 [재귀함수와 완전탐색(DFS:깊이우선탐색)]

1. 문제

<수들의 조합>
: N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개가 있는지 출력하는 프로그램을 작성한다.
예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12 / 2+4+12로 2가지가 있다.
(첫 줄에 정수의 개수 N(3<=N<=20)과 임의의 정수K가 주어지고, 두 번째 줄에는 N개의 정수가 주어진다. 세 번째 줄에 M이 주어진다.)

2. 해결 방법

1. DFS(L, s, sum)을 넘겨준다. sum까지 여기서 처리해주면 좀 더 간편하게 해결할 수 있다.
2. 조합의 핵심은 s에 i+1의 값을 전달하는 거다.

3. 정답

        <script>
            function solution(n, k, arr, m){         
                let answer = 0;
                function DFS(L, s, sum){
                    if(L===k){
                        if(sum%m===0) answer++;
                    }else{
                        for(let i = s; i<n; i++){ //인덱스번호니까 s를 0으로 시작해도 됐다. 핵심은 s에 i+1값을 넘기면 되는 것이므로.
                            DFS(L+1, i+1, sum+arr[i]);
                        }
                    }
                }
                DFS(0, 0, 0);
                return answer;
            }
            let arr=[2, 4, 5, 8, 12];
            console.log(solution(5, 3, arr, 6));
        </script>

        <script> //주석된 부분을 풀어서 올바른 값이 들어갔고 계산이 잘되었는지 보자.
            function solution(n, k, arr, m){         
                let answer = 0;
                //let tmp = Array.from({length:k});
                function DFS(L, s, sum){
                    if(L===k){
                        if(sum%m===0) answer++;
                        //console.log(sum, tmp);
                    }else{
                        for(let i = s; i<n; i++){ 
                            //tmp[L]=arr[i];
                            DFS(L+1, i+1, sum+arr[i]);
                        }
                    }
                }
                DFS(0, 0, 0);
                return answer;
            }
            let arr=[2, 4, 5, 8, 12];
            console.log(solution(5, 3, arr, 6));
        </script>

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

푸하하하핳 스스로 풀었다 푸하하하핳 사실 지금 풀고 있는 문제들이 다 처음 접하는거라 어려운거지 그렇게 어려운 건 없다고 생각한다. 개념응용문젠데 뭐..
근데 꾸준히 안하니까 어려웠던 거 같다. 이 망할 나 자신. 제발 제발 제발 열심히 꾸준히 하자. if(!sum%6) 이러고 헤맸음.(계산결과가 0이면 false니까 true가 될 줄 알았는데.. 아니였음. 아 다시 해보니까 if(!(sum%6))이렇게 하면 됨. 괄호가 필수였네..;) 그래서 console찍어서 해결했다. 그리고 이전에는 tmp[]에 값을 덮어씌웠으니 후작업을 안해줘도 됐는데, 이번엔 sum에 누적하는 것이므로 sum -= arr[i-1];해줘야 올바른 답이 나온다.

        <script>
            function solution(n, k, arr, m){         
                let answer, sum = 0, cnt = 0;
                let tmp = Array.from({length:k}, ()=>0);
                function DFS(L,s){
                    if(L===k){
                        if(sum%6===0) cnt++;
                        else return;
                    }else{
                        for(let i = s; i <= n; i ++){ //i = 1,2,3,4,5
                            sum += arr[i-1]; 
                            DFS(L+1, i+1);
                            sum -= arr[i-1];
                        }
                    }
                }
                DFS(0,1);
                return cnt;
            }
            let arr=[2, 4, 5, 8, 12];
            console.log(solution(5, 3, arr, 6));
        </script>