15649 N과 M (1)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	53007	32674	21798	60.873%

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 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

예제 입력 3

4 4

예제 출력 3

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

코드

import java.io.*;
import java.util.Arrays;

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

        int[] cond = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] sequence = new int[cond[1]];
        find_sequence(sequence, cond[0], 0);
    }

    public static void find_sequence(int[] sequence, int m, int pos) {
        int i = 1;

        while (i <= m) {
            sequence[pos % sequence.length] = i;
            if (is_overlap(sequence, pos % sequence.length)) {
                sequence[pos % sequence.length] = 0;
            }
            else {
                if (pos % sequence.length == sequence.length - 1) {
                    for (int n : sequence) System.out.print(n + " ");
                    System.out.println();
                }
                else find_sequence(sequence, m, pos + 1);
            }
            i++;
        }
    }

    public static boolean is_overlap(int[] sequence, int pos) {
        for (int i = 0; i < pos ; i++) {
            if (sequence[i] == sequence[pos]) return true;
        }
        return false;
    }
}

코드 내용

백트래킹을 통해서 문제를 풀었다.

일단 1부터 m까지 i가 순회하면 종료하는 것으로 재귀문을 작성했다.
sequence라는 변수의 해당 인덱스에 i를 대입하고 중복 체크를 한다.

중복일 경우 넣었던 자리의 값을 0으로 변경한다.
중복이 아닐 경우 현재 pos값이 배열의 끝 부분을 가리키고 있는지 여부를 확인한다.

배열을 모두 채웠을 경우, 하나의 수열이 완성되었다는 의미이므로 수열 출력을 한다.
배열을 모두 채우지 않았을 경우 다음 인덱스를 확인하기 위해 재귀문을 작성한다.

배열이 모두 채워지지 않았고 중복 체크 검사에도 걸리지 않았을 때를 제외하고는 i가 증가하므로 언젠가는 종료 조건을 만족할 수 있다.