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

문제 풀이

---

이번 문제는 유사한 유형인 N과 M (1) 문제처럼 백트래킹을 이용해 풀 수 있다. 사실 저 문제보다 더 쉽게 풀 수 있다.

아이디어 도출

1~N까지 길이가 M인 수열을 선택해야 한다는 조건은 N과 M (1) 문제와 동일하다. 그런데, 이번 문제에서는 수열의 중복 여부가 허용되기 때문에 더 쉽다고 볼 수 있다.

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

1. DFS 재귀함수를 통해 1부터 N까지 탐색한다.
2. 수열의 길이(재귀함수의 깊이)가 M이 된다면 배열에 담아둔 수열을 저장하고 종료한다.

이번 문제에서도 결과로 출력할 수열을 StringBuilder에 담아서 출력하도록 하였다.

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

작성코드

---

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

class Main {    

    // 1. 1~N까지 길이가 M인 수열을 선택해야 한다.
    // 2. 수열 중복이 가능하다. 그렇기에 방문 배열이 필요없다.

    // 수열 배열 선언
    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(0);

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

    }

    /**
     * 백트래킹 DFS 재귀함수
     * 
     */
    public static void dfs(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 길이만큼의 조합을 담아나간다.
         */
        for(int i=1; i<=N; i++) {
            arr[depth] = i;
            dfs(depth + 1);
        }

    }

}

출처

---

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