[백준] 백트래킹 (15652 : N과 M (4))

문제

---

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

15652번: N과 M (4)

---

해설

---

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();

    static int arr[];

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        arr = new int[M];
        dfs15652_2(N, M, 0, 0);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void dfs15652_2(int N, int M, int depth, int pre) {
        if(M == depth){
            for(int i : arr)
                sb.append(i).append(" ");
            sb.append("\n");
            return;
        }

        for (int i = pre; i < N; i++) {
            arr[depth] = i+1;
            dfs15652_2(N, M, depth+1, arr[depth]-1);
        }
    }
}

이번 문제는 15650번 문제와 아주 유사하다고 볼 수 있다.

15650 : N과 M (4) : 2023.09.14 - [CodingTest/백준] - [백준] 백트래킹 (15650 : N과 M (2))

---

15650번 문제는 앞에 나온 수보다 큰 수만 뒤에 올 수 있는 조건이 필요했다면,
이번 문제는 앞의 수와 같은 수부터 올 수 있다.

따라서 재귀함수 호출 시 arr[depth] - 1 (= 현재 값의 -1을 해준 값으로, 다음 재귀함수의 for문에서 해당 값부터 시작하여,
i + 1 해주기 때문에 arr[depth] 값 부터 차례로 호출되는 것임)

---

결론

---

15650번을 풀고 해당 문제를 푸니 간단했던 것 같다.!

---