<수들의 조합>
: 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이 주어진다.)
- DFS(L, s, sum)을 넘겨준다. sum까지 여기서 처리해주면 좀 더 간편하게 해결할 수 있다.
- 조합의 핵심은 s에 i+1의 값을 전달하는 거다.
<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>
푸하하하핳 스스로 풀었다 푸하하하핳 사실 지금 풀고 있는 문제들이 다 처음 접하는거라 어려운거지 그렇게 어려운 건 없다고 생각한다. 개념응용문젠데 뭐..
근데 꾸준히 안하니까 어려웠던 거 같다. 이 망할 나 자신. 제발 제발 제발 열심히 꾸준히 하자. 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>