조합 구하기

27 May 2023 in Algorithm on Java, Coding, Test

문제

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

입력설명

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

출력설명

첫 번째 줄에 결과를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.

입력예제 1

42

출력예제 1

12
13
14

23
24
34

해결방법

• 아래 사진과 같이 가지 뻗는 부분을 저 형태로 외우면 편함.

코드

import java.util.*;

class Main{
  static int[] combi;
  static int n, m;
  public void DFS(int L, int s){
    // 특정 개수를 뽑을 때 까지 진행.  
    if(L==m){
      // 다 뽑았으면, 배열에서 출력한다.  
      for(int x : combi) System.out.print(x+" ");
      System.out.println();
    }
    else{
      // 다 안뽑은 경우 재귀호출을 통해 다음을 진행/반복한다.  
      for(int i=s; i<=n; i++){
        // 뽑은 수 넣는 배열에 값을 넣고
        combi[L]=i;
        // 다음 레벨을 돌린다.
        DFS(L+1, i+1);
      }
    }
  }
  public static void main(String[] args){
    Main.Main T = new Main.Main();
    Scanner kb = new Scanner(System.in);
    n=kb.nextInt();
    m=kb.nextInt();
    combi=new int[m];
    T.DFS(0, 1);
  }
}