[백준 JAVA] 15649 N과 M (1)

15649 N과 M (1)

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

문제설명

1. 수열의 길이는 M이다.
2. 수열의 각 원소는 1부터 N까지의 정수 중 하나이다.
3. 수열은 오름차순으로 정렬되어야 한다

주어진 N과 M에 대해, 가능한 모든 수열을 출력한다.

접근방식

깊이 M까지 탐색: 각 깊이에서 N개의 선택이 가능하므로, M 깊이까지 탐색하면 N^M개의 수열을 생성한다.

각 수열의 처리: 각 수열을 저장하는 데 걸리는 시간은 O(M)이다.

DFS를 사용하여 모든 가능한 수열을 탐색하는 경우 O(N ^ M) 의 시간복잡도가 소요된다.

 

문제 조건 분석 과정

• 깊이 우선 탐색(DFS) 알고리즘을 활용하여 모든 가능한 수열을 탐색하고, 유효한 수열을 찾을 때마다 결과를 저장한다.

전체코드

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

public class Main {
    public static int N, M; // N과 M을 저장할 변수
    public static int[] arr; // 결과를 저장할 배열
    public static StringBuilder sb = new StringBuilder(); // 결과를 문자열로 저장할 StringBuilder

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " "); // 입력 문자열을 공백으로 나누기 위한 StringTokenizer
        N = Integer.parseInt(st.nextToken()); // N 값을 파싱
        M = Integer.parseInt(st.nextToken()); // M 값을 파싱
        arr = new int[M]; // 길이가 M인 배열 생성

        dfs(1, 0); // DFS 호출 (시작 인덱스 1, 깊이 0)
        System.out.println(sb); // 결과 출력
    }

    public static void dfs(int at, int depth) {
        if (depth == M) { // 깊이가 M에 도달하면
            for (int val : arr) { // 배열의 각 값 출력
                sb.append(val).append(' ');
            }
            sb.append('\n'); // 줄바꿈 추가
            return; // 종료
        }
        for (int i = at; i <= N; i++) { // 현재 인덱스 at부터 N까지 반복
            arr[depth] = i; // 배열의 현재 깊이에 i 값을 저장
            dfs(i, depth + 1); // 다음 깊이로 재귀 호출
        }
    }
}