[백준알고리즘] 15649 - N과 M (1)

www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

문제는 위와 같으며 순열을 구현하여 문제를 해결할 수 있습니다. 

 

순열은 n개 중 m개를 순서를 두어 선택하는 것입니다. 즉, [1, 2, 3, 4]라는 수가 있다면 이중 2개를 중복 없이 순서를 두어 뽑는 방법은

[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3] 입니다. 다시 말해, [1, 2]와 [2, 1]은 다르다는 것입니다.

 

 

순열은 매 순간 처음부터 모든 수를 확인하면서 아직 선택되지 않은 경우 그 수를 선택한 것으로 하고 선택한 수를 별도의 배열에 저장한 뒤, 재귀를 통해 다음 수들을 확인하는 방식으로 해결할 수 있습니다.

 

자바 코드는 다음과 같습니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        permutation(new int[n], new boolean[n], n, m, 0);
    }

    // 순열을 구합니다.
    // (뽑힌 실제 숫자 배열, 해당 인덱스를 뽑았는지 아닌지를 결정할 배열, 전체 개수, 뽑아야하는 개수, 실제 뽑힌 개수)
    private static void permutation(int[] nums, boolean[] selected, int n, int r, int depth) {
        // 뽑아야하는 개수를 모두 뽑은 경우
        if (depth == r) {
            // 순서대로 출력하기
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < depth; i++) {
                sb.append(nums[i]).append(" ");
            }
            System.out.println(sb);
            return;
        }

        // 처음부터 뽑아야하는 수를 확인하면서
        for (int i = 0; i < n; i++) {
            if (!selected[i]) {  // 아직 뽑히지 않은 수인 경우
                selected[i] = true;  // 뽑고
                nums[depth] = i + 1;  // 뽑은 수를 저장하고
                permutation(nums, selected, n, r, depth + 1);  // 다음 수를 재귀적으로 확인 (하나 뽑았기 때문에 depth + 1)
                selected[i] = false;  // 해당 위치의 수를 뽑지 않은 경우
            }
        }
    }
}