문제
1부터 N까지의 자연수 중에서 M개를 선택하는 문제다. 같은 수를 여러 번 골라도 되고, 고른 수열은 비감소 순서여야 한다. 즉, 중복 허용 조합(중복 조합)을 구하는 문제다.
입력
- 첫째 줄: N, M (1 ≤ M ≤ N ≤ 8)
출력
가능한 모든 비감소 수열을 사전 순으로 출력 (한 줄에 하나씩)
예제
| 입력 | 출력 |
|---|---|
3 1 | 1 2 3 |
3 2 | 1 1 1 2 1 3 2 2 2 3 3 3 |
풀이
DFS(백트래킹)로 중복 허용 조합을 생성한다. N과 M (2)의 조합과 달리, 같은 수를 다시 선택할 수 있으므로 재귀 호출 시 dfs(i, depth + 1) (같은 인덱스 i를 유지)로 호출한다.
dfs(at, depth)함수에서at은 탐색 시작 숫자,depth는 현재까지 선택한 수의 개수다.depth == M이면 결과 배열을 출력하고 반환한다.at부터 N까지 순회하며 현재 깊이에 숫자를 저장한다.dfs(i, depth + 1)로 호출 — 다음 재귀에서i부터 다시 선택 가능하여 중복이 허용된다.
핵심 아이디어: N과 M (2)의 dfs(i + 1, ...) 대신 dfs(i, ...)를 호출하는 단 하나의 차이로 중복 조합이 구현된다. 시작 인덱스를 현재 값과 같게 유지하면 현재 숫자를 또 선택할 수 있다.
코드
package com.ssafy.an.day049;
import java.util.Scanner;
public class Day43BOJ15652N과M4DFS연습 { // 15652 N과 M(4) DFS
static int[] arr;
static int N, M;
static StringBuilder sb;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
sb = new StringBuilder();
N = sc.nextInt();
M = sc.nextInt();
arr = new int[M];
dfs(1, 0);
System.out.println(sb);
sc.close();
}
static void dfs(int at, int depth) {
if (depth == M) {
for (int n : arr) {
sb.append(n).append(" ");
}
sb.append("\n");
return;
}
for (int i = at; i <= N; i++) {
arr[depth] = i;
dfs(i, depth + 1);
}
}
}복잡도
- 시간: O(C(N+M-1, M)) — 중복 조합의 수
- 공간: O(M) — 재귀 호출 스택 깊이와 결과 배열