[Java] 백준(실버-3) 15652번 - N과 M (4)

문제 풀이

---

이번 문제는 유사한 유형인 N과 M (2) 문제처럼 백트래킹을 이용해 풀 수 있다.

아이디어 도출

오름차순 수열을 유지해야 하는 N과 M (2) 문제와 유사해보이지만, 이번 문제에서는 비내림차순으로 중복 여부가 허용됨을 고려해야 한다.

재귀함수를 어떻게 짜야 할까?

여기서도 깊이를 의미하는 depth와 함께 현재 위치를 의미하는 at을 함께 사용해야 한다. 비내림차순으로 중복 여부가 허용되기에 1부터 N까지 탐색하며 다음 재귀를 호출할 때 i값을 at으로 넘겨 재귀호출하면 된다.

N과 M (2) 문제처럼 오름차순으로 수열을 담기 위해 i+1 값을 at으로 넘겨주는 것이 아니라, 비내림차순으로 현재 위츼 i값도 허용되기에 i+1값이 아닌 i값을 at으로 넘겨준다.

문제 풀이를 위한 아이디어는 다음과 같다.

1. DFS 재귀함수를 통해 1부터 N까지 탐색한다.
2. 탐색하며 재귀 호출할 때 현재 위치를 의히마는 at 변수와 깊이인 depth 변수 2가지를 인자로 호출한다.
3. 비내림차순의 수열을 유지하기 위해 중복이 허용되도록 1 ~ N까지 탐색할 때, at 변수를 현재 위치 i값으로 다음 재귀를 호출하며 수열을 갱신한다.
4. 수열의 길이(재귀함수의 깊이)가 M이 된다면 배열에 담아둔 수열을 저장하고 종료한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    // 1. 1~N까지 길이가 M인 수열을 선택해야 한다.
    // 2. 선택한 수열은 비내림차순이어야 한다. (비내림차순 != 오름차순)
    // 3. 중복 여부를 고려하지 않으므로 중복이 허용된다.

    // 수열 배열 선언
    static int[] arr;

    // 입력 N, M 선언
    static int N, M;

    // 출력할 수열을 담을 StringBuilder 선언
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        try (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(1, 0);

                bw.write(sb + "\n");
                
        }

    }

    /**
     * 백트래킹 DFS 재귀함수
     */
    public static void dfs(int at, int depth) {

        // 재귀 인덱스가 마지막 위치인 M이 된다면 수열을 sb에 담은 후 종료
        if(depth == M) {
            for(int i=0; i<M; i++) {
                sb.append(arr[i]).append(" ");
            }
            sb.append("\n");
            return;
        }

        /**
         * 1부터 N까지 깊이를 1씩 증가시키며 DFS를 재귀호출한다.
         * arr 배열에 M 길이만큼의 조합을 담아나간다.
         * 오름차순과는 다르게 비내림차순으로 중복이 허용되기에 동일한 i값을 at으로 넘겨준다.
         */
        for(int i=at; i<=N; i++) {
            arr[depth] = i;
            dfs(i, depth + 1);
        }

    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.