[인프런/DFS/8. 수열 추측하기]

<<풀이>>

 

후.. 일단 너무 피곤한 상태로 풀어서 그런지 머리가 안 돌아갔다. 물론 어려운 문제이기도 하다 ㅠㅠ 내 혼자 힘으로 풀어 보고 싶지만

너무 시간 잡아 먹는 것도 좋지 않기 때문에 어느 정도 선에서 풀이를 보고자 한다.,

밑의 코드는 내가 한 곳 까지 적어놨다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {
    private int combi(int n, int i) {
        int[][] ch = new int[11][11];
        if (ch[n][i] > 0) return ch[n][i];
        if(n == i || i == 0) return 1;
        else return ch[n][i] = combi(n - 1, i - 1) + combi(n - 1, i);
    }

    private ArrayList<Integer> solution(int n, int m) {
        int[] combiresult = new int[n];
        for (int i = 0; i < n; i++) {
            combiresult[i] = combi(n - 1, i);
        }

       return answer(combiresult, n, m);

    }

    private ArrayList<Integer> answer(int[] combiresult, int n, int m) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.get()
        }

    }

    public static void main(String[] args) throws Exception{
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);

        for (int x : T.solution(n, m) ) {
            System.out.print(x + " ");
        }
    }
}

 

 

-강사님 풀이-

 

역시 깔끔 그 자체 ,,, 이때 까지 가르쳐 주신 것을 야무지게 조합해서 푸셨다.!!! 이런 감각 나도 가지고 싶다 ㅠㅠ

 

결국 내가 푼 방식의 흐름을 가지고 있지만, 코드 자체는 훠얼씬 깔끔하고 트렌디 하다!!

 

지금은 이렇게 풀다가 막히고 하지만, 미래의 나는 강사님처럼 잘했으면한다 ㅎㅎ .. 화이팅!

import java.util.*;
class Main{
    static int[] b, p, ch;
    static int n, f;
    boolean flag=false;
    int[][] dy=new int[35][35];
    public int combi(int n, int 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);
    }

    public void DFS(int L, int sum){
        if(flag) return;
        if(L==n){
            if(sum==f){
                for(int x : p) System.out.print(x+" ");
                flag=true;
            }
        }
        else{
            for(int i=1; i<=n; i++){
                if(ch[i]==0){
                    ch[i]=1;
                    p[L]=i;
                    DFS(L+1, sum+(p[L]*b[L]));
                    ch[i]=0;
                }
            }
        }
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt();
        f=kb.nextInt();
        b=new int[n];
        p=new int[n];
        ch=new int[n+1];
        for(int i=0; i<n; i++){
            b[i]=T.combi(n-1, i);
        }
        T.DFS(0, 0);
    }
}