조합 구하기

설명

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

 

입력

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

 

출력

첫째 줄에 결과를 출력합니다.

출력순서는 사전순으로 오름차순으로 출력합니다.

 

예시 입력 1 

4 2

 

예시 출력 1

1 2 
1 3 
1 4 
2 3 
2 4 
3 4

 

 

문제 해결

 

1부터 N까지 번호가 적힌 구슬 중에서 M개를 뽑는 모든 조합을 출력하는 문제이다.

모든 조합을 출력해야하므로 DFS 를 이용해보자.

 

static int N, M;
static int[] bead, selected;
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    N = in.nextInt();
    M = in.nextInt();

    bead = new int[N];
    selected = new int[M];

    for(int i = 0; i < N; i++) {
            bead[i] += i+1; //1부터 시작
        }

    DFS(0,0);

• 구슬의 개수 N 과 선택할 구슬 M을 static 변수로 선언해준다.
• bead는 N까지의 구슬 번호를 저장하는 배열이고 (크기 : N)
• selected는 선택된 M개의 구슬 번호를 저장하는 배열이다. (크기 : M)
• board 배열에 1부터 N까지의 숫자를 넣어준다. i가 0부터 시작되므로 i+1을 넣어주면 된다.

 

public static void DFS(int L, int start) {
    if(L == M) {
        for(int num : selected){
            System.out.print(num + " ");
        }
        System.out.println();
        return;
    }

    for(int i = start; i < N; i++) {
        selected[L] = bead[i];
        DFS(L+1, i+1); //시작점 변경
    }


}

• L은 레벨, start는 선택할 구슬의 시작 인덱스를 의미한다.
  • L이 M과 같아지면, selected 배열에 저장된 M개의 구슬 번호를 그대로 출력하고
  • 같지 않으면, 아직 선택할 경우가 남아있다는 의미이므로 start 인덱스부터 N까지 반복하여 구슬을 선택해 selected에 넣어주고 다음 DFS를 호출한다.
    • 이 때 i+1을 넘겨주어 start 지점을 변경하여 현재 구슬보다 이후에 있는 구슬만 선택될 수 있도록 해야한다. 

 

최종 코드

 

import java.util.Date;
import java.util.Scanner;

public class P09_조합구하기 {
    static int N, M;
    static int[] bead, selected;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();

        bead = new int[N];
        selected = new int[M];

        for(int i = 0; i < N; i++) {
            bead[i] += i+1; //1부터 시작
        }

        DFS(0,0);

    }

    public static void DFS(int L, int start) {
        if(L == M) {
            for(int num : selected){
                System.out.print(num + " ");
            }
            System.out.println();
            return;
        }

        for(int i = start; i < N; i++) {
            selected[L] = bead[i];
            DFS(L+1, i+1); //시작점 변경
        }


    }

}