백준 15649 N과 M

15649번: N과 M (1)Baekjoon Online Judge

Solution 1. 재귀함수,visited

• 79996 kb / 2980 ms

• 1부터 N까지의 자연수 중에서 M개를 중복없이 뽑는 경우의 수를 구하는 문제이므로 순열 알고리즘을 사용했다.

  • visited 를 이용하여 dept 가 깊어질수록 하나씩 고정되어 트리의 앞쪽부터 순서대로 찾아 depth와 일치되는 즉시 출력하도록 하였다.

  • 참고) https://bcp0109.tistory.com/14

package practice.algorithm.math;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Bj_15649 {
    private static int n, m;

    public static void main(String[] args) throws IOException {
        input();

        int[] output = new int[m];
        boolean[] visited = new boolean[n];

        permutation(n, m, 0, visited, output);
    }

    private static void permutation(int n, int m, int depth, boolean[] visited, int[] output) {
        if (depth == m) {
            printOutput(output);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                output[depth] = i+1;
                permutation(n, m, depth+1, visited, output);
                visited[i] = false;
            }
        }
    }

    private static void printOutput(int[] output) {
        for (int o : output) {
            System.out.print(o + " ");
        }
        System.out.println();
    }


    private static void input() 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());
    }
j