BOJ 15649번 N과 M (1)

문제

 

www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

접근 |

1. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
2. swap방식의 순열 알고리즘을 사용하면 사전식 출력 조건에 벗어남
3. DFS 방식의 순열 알고리즘 선택 접근

 

풀이

1. 1부터 N까지 숫자를 하나씩 고르고 순열 함수 재귀 호출
2. checked 배열로 현재 숫자를 뽑았는지 체크
3. 현재 뽑은 숫자 카운트를 인덱스로 사용하여 arr 배열에 저장
4. 카운트가 M이 되면 뽑은 숫자 출력 후 리턴
5. 재귀 호출이 끝나면 방문 체크 해제

 

 

class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int N;
    static int M;
    static boolean[] checked;
    static int[] arr = new int[10];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = stoi(st.nextToken());
        M = stoi(st.nextToken());

        checked = new boolean[N+1];

        permutation(0);
    }

    static void permutation(int r){
        if(r == M){
            for (int i = 0; i < M; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= N; i++) {
            if(checked[i]) continue;
            checked[i] = true;
            arr[r] = i;
            permutation(r+1);
            checked[i] = false;
        }
    }
}