[Baekjoon] 15650 - N과 M (2)

📝 문제

 

 

🔑 풀이 과정

· 앞서 풀이한 15649번 문제와 비슷한 백트래킹 문제이다.

15649번 풀이는 여기 ↓

https://seohyun0916.tistory.com/292

[Baekjoon] 15649 - N과 M (1)

 

· 이 문제는 15649번 문제에서 조건이 하나 더 추가된 문제이다.

추가된 조건: 고른 수열은 오름차순이어야 한다.

→ 이는 depth가 i일때 들어갈 수 있는 수는 i-1의 depth에 위치하는 수보다 무조건 커야된다는 뜻이다.(ex. 1 2 3 4)

 

· DFS함수에서 depth만 인자로 넘겨주었던 15649번 문제와 달리,

이 문제는 수열을 오름차순으로 만들기 위해 숫자 하나를 더 인자로 넘겨줄 것이다.

DFS(int n, int depth)
여기서 depth는 현재 채워야 할 depth 이며,
n은 현재depth - 1에 위치한 값을 의미한다.

예를들어 DFS(2, 2)는
depth 1이 가리키는 값은 2고, 지금 depth 2일때를 탐색한다는 것

 

· 15649번 문제는 어느 depth든 1부터 N까지 순회하면서 방문하지 않은 값을 탐색해야 하므로 방문배열을 추가해주었었다.

그러나 이번 문제는 오름차순이라는 조건 때문에 이전 depth의 값 다음 부터 N까지 탐색한다. 순회 범위가 정해져있으므로 방문배열을 사용해 줄 필요가 없다.

또한 DFS함수는 depth가 M이 되면 현재까지 채워진 배열을 출력하게 돼있다. 만약 조건을 만족하는 수열을 만들지 못한다면 depth가 M까지 갈 수 없기때문에 그냥 자동적으로 출력되지 않는다.

 

 

 

🔓 답안

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

public class Main {

    static StringBuilder sb = new StringBuilder();

    static int N;
    static int M;

    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        //---입력 종료

        arr = new int[M];

        DFS(0, 0);

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

    static void DFS(int n, int depth){
        if(depth == M){
            for(int num : arr){
                sb.append(num).append(" ");
            }
            sb.append("\n");
            return;
        }

        for(int i = n + 1; i <= N; i++){
            arr[depth] = i;
            DFS(i, depth + 1);
        }
    }

}

 

 

 

🖤 알고리즘 분류

- 백트래킹