2022/04/25) 13. 수열 추측하기 [재귀함수와 완전탐색(DFS:깊이우선탐색)]

1. 문제

<수열 추측하기>
: 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4이고 가장 윗 줄에 3 1 2 4가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.
N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성한다. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력해야 한다.
(첫 번째 줄에 두 개의 정수 N(1<=N<=10)과 F가 주어진다. 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.)

2. 해결 방법

1. 그림을 그려본다.
   그러면 아래처럼 나오는데, 결국 숫자의 위치에 따라 몇 번을 더해야 하는지 개수가 정해진다.
2. 다른 예시도 한 번 봐보자.
   결국 n-1C0 ... n-1Cn-1을 구해야 하는 것이다.
   
3. 그렇다면 이제 문제를 풀어보자. 1부터 N까지의 숫자가 주어지면, 이 숫자가 어떻게 배치돼 있느냐에 따라서 결과가 달라진다. 그러므로 우선 앞에서 배운 순열(1,2,3,4 / 1,2,4,3 / ...)이 들어가고, 이미 구했던 값을 중복해서 구할 필요는 없으므로 메모이제이션 또한 넣어보자.
   규칙을 배열로 만들고(+콤비네이션계산(combi함수)), DFS에서 순열 만들어서 합을 구하자.
4. 정리하자면, 규칙을 만들기 위해 for문을 돌려서 combi함수 호출해서 계산하여 b배열 완성하고, DFS-else문에서 순열 만들어서 합을 구해서(p배열 이용), DFS-if문에서 검증하기.

• flag 변수가 있는 이유는 가장 앞에 오는 것을 출력하라고 했으므로.

3. 정답

        <script>
            function solution(n, f){         
                let answer, flag=0;
                let dy= Array.from(Array(11), () => Array(11).fill(0)); //n의 범위가 1<=N<=10이라고 했으므로. 메모이제이션
                let ch=Array.from({length:n+1}, ()=>0); //for문을 1부터 n까지 돌리므로, 길이를 n으로 할 경우 모자란다.(인덱스때문에)
                let p=Array.from({length:n}, ()=>0); //순열
                let b=Array.from({length:n}, ()=>0); //규칙
                function combi(n, r){ //메모이제이션
                    if(dy[n][r]>0) return dy[n][r];
                    if(n===r || r===0) return 1;
                    else return dy[n][r]=combi(n-1, r-1)+combi(n-1, r);
                }
                function DFS(L, sum){
                    if(flag) return; 
                    if(L===n && sum===f){
                        answer=p.slice();
                        flag=1; //답이 구해졌으면 끝낸다.
                    }
                    else{
                        for(let i=1; i<=n; i++){ //순열만들기(1,2,3,4 / 1,2,4,3 / ...) + 값(규칙) //1부터 돌리는 이유 : 순열을 구하기 위한 것이므로 1,2,3,4의 수가 쓰여야 하므로
                            if(ch[i]===0){
                                ch[i]=1;
                                p[L]=i;
                                DFS(L+1, sum+(b[L]*p[L])); //위치에 따라 곱해야 할 개수가 정해진다고 했다. 계산(개수*값)
                                ch[i]=0;
                            }
                        }
                    }
                }
                for(let i=0; i<n; i++){ //규칙(1,3,3,1) //0부터 돌리는 이유 : 콤비네이션 r이 0부터 3까지 쓰이므로
                    b[i]=combi(n-1, i); //b[0]=3C0, b[1]=3C1, b[2]=3C2, b[3]=3C3 
                }
                DFS(0, 0);
                return answer;
            }
            console.log(solution(4, 16));
        </script>

        <script> //ch배열 인덱스가 헷갈려서 그냥 이렇게 바꿔버림
            function solution(n, f){//answer, flag, dy, ch, p(순열), b(규칙) /L, sum                let answer, flag = 0;
                let dy = Array.from(Array(n), ()=> Array(n).fill(0));
                let ch = Array.from({length:n}, ()=>0);
                let p = Array.from({length:n}, ()=>0);
                let b = Array.from({length:n}, ()=>0);
                function combi(n, r){
                    if(dy[n][r]>0) return dy[n][r];
                    if(n===r || r===0) return 1;
                    else return dy[n][r] = combi(n-1, r-1) + combi(n-1, r);
                }
                function DFS(L, sum){
                    if(flag) return;
                    if(L===n && sum === f){
                        answer = p.slice();
                        flag = 1;
                    }else{
                        for(let i = 1; i <= n; i ++){ 
                            if(ch[i-1] === 0){
                                ch[i-1] = 1;
                                p[L] = i;
                                DFS(L+1, sum+(p[L]*b[L]));
                                ch[i-1] = 0;
                            }
                        }
                    }
                }
                for(let i = 0; i < n; i ++){
                    b[i] = combi(n-1, i);
                }
                DFS(0,0);
                return answer;
            }
            console.log(solution(4, 16));
        </script>