[BOJ/Java] 15652. N과 M (4)

[BOJ/Java] 15652. N과 M (4)

15652번: N과 M (4)

---

문제 해석

이 문제에서는 1부터 𝑁까지의 수 중에서 중복을 허용하여 𝑀개를 고르는 조합을 모두 찾는다. 선택된 수열은 비내림차순이어야 한다는 조건이 있어, 각 수열의 원소는 이전 원소보다 작아지지 않는다.

풀이 과정

문제의 요구 사항을 충족시키기 위해 재귀 함수를 사용하여 문제를 해결한다. 주어진 문제는 백트래킹 기법을 이용해 풀 수 있다. 재귀적으로 각 위치에 들어갈 수를 결정하고, 이전 선택된 수 이상의 숫자만을 다음 위치에 넣어주면서 수열을 완성한다.

코드

package edu.ssafy.im.BOJ.Silver.S3.No15652;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().sol();
    }

    private int N; // 최대 숫자 범위
    private int M; // 수열의 길이
    private int[] sel; // 현재까지 선택된 수를 저장하는 배열
    private StringBuilder sb = new StringBuilder(); // 출력을 위한 문자열 빌더

    private void sol() 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());
        sel = new int[M]; // M 크기의 배열 초기화

        recursion(0, 0); // 재귀적 조합 생성 시작

        bw.write(sb.toString()); // 결과 문자열 출력
        bw.flush();
        bw.close();
    }

    private void recursion(int k, int idx) {
        if (k == sel.length) { // 재귀의 끝, 수열이 완성되었을 때
            for (int s : sel) sb.append(s).append(" "); // 수열을 문자열로 변환
            sb.append("\n");
            return;
        }
        for (int i = idx; i < N; i++) { // 현재 인덱스에서 N까지 숫자 선택
            sel[k] = i + 1; // 선택된 숫자 저장 (1부터 시작)
            recursion(k + 1, i); // 다음 숫자 선택을 위한 재귀 호출
        }
    }
}

시간 복잡도 분석

이 코드의 시간 복잡도는 재귀의 깊이 𝑀과 반복문의 실행 횟수 𝑁에 의해 주로 결정된다. 최악의 경우 시간 복잡도는 𝑂(𝑁𝑀)이 될 수 있다.

느낀점

재귀를 사용하여 복잡한 조합을 간결하고 효과적으로 생성하는 방법을 배울 수 있었다. 이 문제는 백트래킹의 기초적인 형태를 이해하고 익히기에 적합하며, 다양한 재귀 문제에 대한 접근 방법을 배울 수 있었다.