[백준] 백트래킹 (15650 : N과 M (2))

문제

---

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

15650번: N과 M (2)

---

해설

---

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];
        dfs15650_2(N, M, 0, 0);

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

    private static void dfs15650_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;
            dfs15650_2(N, M, depth+1, arr[depth]);
        }
    }
}

이전문제와 비슷하지만 이전 문제는 (1,2) != (2,1)이었다면 이번 문제는 이를 동일한 경우로 생각한다.

따라서 이러한 경우를 제거해주기 위해서, 여러 경우의 수를 확인해보던 중 아래와 같은 규칙을 발견할 수 있었다.

1) N = 4, M = 2 (왼쪽)

2) N = 4, M = 3 (가운데)

3) N = 5, M = 2 (오른쪽)

해당 결과를 보면, 앞서 나온 수보다 그 다음 나온 수가 무조건 더 큰 것을 확인할 수 있다.

그렇다면, 이를 위해서 재귀함수를 호출할 때 그 이전의 값을 인자로 넘겨주고,
해당 수보다 큰 값들만을 탐색하면 해결될 것이라고 생각했다.

---

1. 이전 문제와 마찬가지로 M == depth일 때, 재귀함수 탈출
2. 재귀함수의 매개변수로 arr[depth]를 넣어주어, 재귀함수의 내부의 for문에 int i = pre를 통해 이전 수부터 시작하면,
   arr[depth] = pre + 1부터 배열을 채워갈 것이므로 해당 방법으로 문제를 해결할 수 있었다.

---

결론

---

이전 문제에 조금 얽매여 있었어서 조금 오래 고민했던 것 같다.

하나의 경우만 생각하지 말고 나도 백트래킹 알고리즘 처럼 아닌거 같으면 돌아가서 다시 생각해볼 수 있도록 해야겠다
(•͈⌔•͈⑅)

---