[BOJ] 15650. N과 M(2)(조합 기본).java

#. Problem

https://www.acmicpc.net/problem/15650

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이 문제는 N개의 자연수 중에서 중복 없이 M개를 고른 수열을 만드는 조합 문제다.

조합 : 서로 다른 n개의 원소 중에서 중복을 허락하지 않으며 순서를 생각하지 않고 r개를 택할 때

조합은 중복을 허락하지 않고, 순서를 생각하지 않는다.

그러므로

1 2

2 1 

이 같다고 받아들여진다.

조합은 순서를 생각하지 않기 때문에,

1과 2를 골라서 나온 순열이라면 다 같은 경우라는 것이다

그래서 Input이

4 2

로 주어질 때, Output은

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

가 되는 것이다.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ15650 {
    
    static int N, M;
    static int arr[];
    static boolean visited[];
    static int sel[];
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        // init
        arr = new int[N];
        visited = new boolean[N];
        sel = new int[M];
        for (int i = 0; i < N; i++) 
            arr[i] = i+1;
        
        process(0, 0);
        System.out.println(sb);
    }
    
    public static void process(int idx, int cnt) {
        if(cnt == M) {
            int x = 0;
            for (int j = 0; j < N; j++) {
                if(visited[j]) {
                    sb.append(sel[x++] + " ");
                }
            }
            sb.append('\n');
            return;
        }
        // 이미 골라진 숫자를 다시 고를 수 없도록
        // 다음 idx부터 자연수를 선택
        for (int i = idx; i < N; i++) {
            // 중복을 허용하지 않으므로
            // 사용하지 않은 자연수일 경우
            if(!visited[i]) {
                // 이 자연수를 사용해보자.
                visited[i] = true;
                sel[cnt] = arr[i];
                // 위 자연수를 사용했으므로 idx + 1, cnt + 1
                process(i + 1, cnt+1);
                
                // 이 자연수를 사용하지 않을래.
                visited[i] = false;
            }
        }
    }
}