(15650) N 과 M(2)

문제

문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다.

입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

문제 풀이

해당 문제는 순열중에서 조합과 관련된 문제이다. 조합은 순열과 달리 순서의 배치에 따라 다른 집합으로 보지 않기 때문에 중복된 숫자가 나올 수 없다. 그렇기 때문에 이러한 특성을 기억을 하고 재귀호출시 어떻게 해야 하는지 곰곰히 생각해봐야 하는 문제이다. 

 

기본적으로 1 ~ n 까지의 숫자에서 길이 m이 되면은 출력이 되는 문제에서 추가적으로 매개변수를 하나 더 받아서 for문을 시작할 때 시작값을 잘 지정해주면 되는 문제이다. 

 

아래 반복문에서 현재 입력한 숫자 j 를 재귀함수시 j + 1값을 넘겨 줌으로써 조합의 특성을 지킬 수 있다.

for (int j = i; j < n; j++) {
    if (!visited[j]) {
        visited[j] = true;
        arr[depth] = j + 1;
        solution(n, m, depth + 1, j + 1);
        visited[j] = false;
    }
}

---

나의 답안

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

public class Main {
    static int[] arr;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        arr = new int[n];
        visited = new boolean[n];

        solution(n, m, 0, 0);
    }

    private static void solution(int n, int m, int depth, int i) {
        if (depth == m) {
            for (int j = 0; j < m; j++) {
                System.out.print(arr[j] + " ");
            }
            System.out.println();
            return;
        }

        for (int j = i; j < n; j++) {
            if (!visited[j]) {
                visited[j] = true;
                arr[depth] = j + 1;
                solution(n, m, depth + 1, j + 1);
                visited[j] = false;
            }
        }
    }
}