algorithm - 조합 경우의수, 수열 추측하기, 조합 구하기

조합 경우의 수

public class ex7 { 
    static int[][] ch = new int[35][35];

    public static int DFS(int n,int r){
        if(ch[n][r]>0) return ch[n][r];
        if(n==r||r==0) return 1;
        else{
            return ch[n][r] = DFS(n-1,r-1) + DFS(n-1,r);
        }
    }

    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);

        int n = sc.nextInt();
        int r = sc.nextInt();

        System.out.println(DFS(n,r));
    }
}

이 식을 구현 한 문제. 메모이제이션 활용.

수열 추측하기

public class ex8 {

    static int[] ch,b,p;
    static int[][] dy = new int[35][35];
    static int n,f;

    public static 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);
        }
    }

    static boolean flag = false;
    public static 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) {
        Scanner sc = new Scanner(System.in);

        n= sc.nextInt();
        f= sc.nextInt();
        b = new int[n];
        p = new int[n];
        ch = new int[n+1];

        for(int i=0; i<n; i++){
            b[i] = combi(n-1,i);
        }
        DFS(0,0);
    }
}

수열 추측하기
수열 추측하기는 규칙을 가진다
3 1 2 4
4 3 6
7 9
16

입력 4 16

여기서 4자리 숫자로 16을 만드는 조합경우의수 의 숫자는 3 1 2 4 인데
4자리 숫자의 조합 경우 -> '3C0 3C1 3C2 3C3' 을 각각 해당 자리 수랑 곱해서 더했을 때 16이 된다.
이 문제에서는 해당 조합경우의수와 곱했을 때 16이 되는 '수' 를 구해야한다.

조합 구하기

public class ex9 {
    static int n,m;
    static int ch[],answer[];
    public static void DFS(int L,int s){
        if(L==m) {
            for(int x : answer) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
        else{
            for(int i=s; i<=n; i++){
                if(ch[i]==0){
                    ch[i]=1;
                    answer[L]=i;
                    DFS(L+1,i+1); //핵심
                    ch[i]=0;
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        answer = new int[m];
        ch = new int[n+1];
        DFS(0,1);
    }
}

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.

이 문제는 뽑았던 수를 계속 뽑으면 안되고 안겹치게 N의 숫자에서 M개를 뽑는 경우의 수를 구해야한다.

n이 4라고 한다면,
1 -> 2,3,4
2 -> 3,4
3 -> 4
4 -> x
이렇게 DFS가 뻗어나가야한다. 재귀 호출 : DFS(L+1,i+1)