[자바] BOJ_15652_N과M(4)_S3

동동주·2025년 12월 1일

코딩테스트

목록 보기

9/16

🧩 BOJ 15652 — N과 M (4)

중복 조합(Combination with Repetition)

📌 문제 요약

N과 M이 주어졌을 때,

1부터 N까지 자연수 중에서
중복을 허용해서
비내림차순(오름차순 유지)으로
길이가 M인 수열을 모두 출력

예:
N=4, M=2라면

이런 식의 "중복 조합" 형태가 나온다.

핵심 개념 정리

✔ 왜 start 파라미터가 필요할까?

중복은 허용하지만
비내림차순(이전 값보다 작으면 안 됨) 을 유지해야 한다.

즉,

이전에 선택한 값(i)을 다음 depth에서도 최소값으로 유지해야
오름차순이 유지됨
그래서 for (int i = start; i <= N; i++) 로 시작

start 가 핵심이다.

흐름 시각화 - 헷갈렸음..

예시: N=3, M=2

depth=0, start=1

dfs(0,1)
 └ i=1 → arr[0]=1
       → dfs(1,1)
           └ i=1 → arr[1]=1 → dfs(2,1) → 출력: 1 1
           └ i=2 → arr[1]=2 → 출력: 1 2
           └ i=3 → arr[1]=3 → 출력: 1 3
           └ i=4 → arr[1]=4 → 출력: 1 4
 └ i=2 …

시간 복잡도

전체 탐색 개수

중복 조합의 개수는

N,M ≤ 8 이므로 최대 약 6435개 정도.

한 수열을 만드는 비용

배열 8개 채우는 수준 → O(M)

🔥 전체 시간

6천 × 8
= 약 5만 연산

➡ Java에서는 0.001초 수준
➡ 시간초과 걱정 전혀 없음

✅ 최종 코드

package algo.ct.M11;

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

public class BOJ_15652_N과M4_S3 {
    static int[] arr;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[M];

        dfs(0, 1);
    }

    public static void dfs(int depth, int start) {
        if (depth == M) {
            for (int i = 0; i < M; i++)
                System.out.print(arr[i] + " ");
            System.out.println();
            return;
        }

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