[백준] java 15650 N과 M (2)

https://www.acmicpc.net/problem/15650

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

풀이과정

바로 전 문제인 N과 M (1)과 유사한 문제이다. 출력 조건에 차이점이 한 가지가 있는데, 바로 중복 없이 M개를 고른 수열이여야한다는 점이다. 가령 입력이 N=4,M=2라고 생각해보면, 다음과 같이 나타내야한다.

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

2 1를 제외하고 2 3, 2 4가 출력되어있는데, 1 2와 2 1은 중복되는 수열이다. 또한, 3 1, 3 2도 제외되어있는데, 마찬가지로 1 3과 2 3이 이미 존재하기에 중복된 수열이므로 출력시키지 않은 것으로 보인다.

그런데 여기서 중요한 점이 있다. 제외된 수열과 출력된 수열의 차이를 보면 한 가지 공통점이 보인다.

N=3, M=2일 때를 보자.

아래 세 개의 수열이 중복으로 제외된다.
2 1
3 1
3 2

출력되어야하는 수열과의 차이점은 바로, 출력된 수열은 모두 오름차순이고 제외된 수열은 모두 오름차순이 아니다.

위의 N=4,M=2의 경우에도 마찬가지이다. 제외된 수열은 다음과 같이 오름차순이 아니므로 모두 제외되고 오름차순인 수열만 출력이 되어있다.
2 1
3 1
3 2

이 같은 공통점으로 다음과 같이 문제를 풀 수 있다.

public class Main {
    static int M;
    static int N;
    static int[] arr = new int[10];
    static boolean[] isUsed = new boolean[10];
    static StringBuilder sb = new StringBuilder();
    public static void solve( int index, int k ){
        if( index == M ){
            for( int i = 0; i < M; i++ )
                sb.append(arr[i]).append(" ");
            sb.append("\n");
            return;
        }
        for( int i = k; i <= N; i++ ){
            if( !isUsed[i] ){
                arr[index] = i;
                isUsed[i] = true;
                // 오름차순이어야하므로
                // k에 i+1을 매개변수로 사용
                solve(index+1, i+1);
                isUsed[i] = false;
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        solve( 0, 1 );
        System.out.println(sb);
    }
}

1부터 N까지 모든 수에 대해 트래킹을 하는 것이 아닌 i+1을 넣어 오름차순으로 트래킹하도록 작성하였다.