[백준] Silver 3. N과 M(2)

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

15650번: N과 M (2)

 

문제 요구 사항

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

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

public class Main {

    static int m, n;
    static int [] arr = new int[10];
    static boolean[] visited = new boolean[10];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) 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());
        recur(1, 0);
        System.out.println(sb.toString());
    }

    private static void recur(int start , int depth) {
        if (depth == m) {
            for(int i = 0; i < m; i++){
                sb.append(arr[i]).append(' ');
            }
            sb.append("\n");
            return;
        }
        for(int i = start; i <= n; i++) {
            if (!visited[i]) {
                arr[depth] = i;
                visited[i] = true;
                recur(i + 1, depth + 1);
                visited[i] = false;
            }
        }
    }
}

 

문제 풀이 회고

 

재귀를 돌릴 때

recur(start + 1, depth + 1);

이렇게 설정하다보니 

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

 

이렇게 오름차순에 위배되는 숫자쌍인 (3,2), (4,2), (4,3)이 출력되었다.

 

start + 1이랑 i + 1이랑 다른게 뭘까?

 

start + 1인 경우, 다음 재귀 호출에서 시작 범위만을 변경한다. recur(start + 1, depth + 1)에서는 다음 호출에서의 시작 위치를 start + 1로 변경하여 순열을 생성합니다. 이 때 현재 선택한 숫자 이후의 숫자들만을 포함하여 순열을 구성해준다.

 

recur(i + 1, depth + 1) 은 이전 호출에서 선택한 숫자 이후의 숫자들을 대상으로 순열을 생성하는 방식을 나타내준다.