[백준(JAVA)] 15650번: N과 M (2)

문제

✔ 난이도 - Silver 3

설명

https://velog.io/@seha01130/백준JAVA-15649번-N과-M-1 와 비슷한 문제지만 순열이 오름차순이라는 조건이 추가되었다.

result는 M개의 선택한 순열을 담을 int 배열
flagNum 변수는 기준이 되는 숫자이다. 이 숫자 이후로 오름차순이 되어야 함. 따라서 1로 초기화를 한 후 dfs를 시작한다.

flagNum 수부터 시작해서 N까지 for문을 도는데 다음 depth로 갈때는 현재 선택한 수보다 큰 수부터 시작해야하므로 dfs에 인자를 넘겨줄 때, i + 1을 flagNum으로 넘겨준다.

풀이

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        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());

        int[] result = new int[M];
        int flagNum = 1; // 기준이 되는 숫자. 이 숫자 이후로 오름차순이 되어야함.
        int depth = 0;

        dfs(N, M, depth, result, flagNum);

        System.out.println(sb);
    }

    public static void dfs(int N, int M, int depth, int[] result, int flagNum){
        // result가 다 찼으면 출력
        if (depth == M) {
            for (int i = 0; i < M; i++){
                sb.append(result[i] + " ");
            }
            sb.append("\n");

            // return 하는거 빼먹으면 안됨!!!
            return;
        }

        for (int i = flagNum; i <= N; i++){
            result[depth] = i;
            dfs(N, M, depth + 1, result, i + 1);
        }
    }
}