문제
N개의 자연수 중에서 M개를 고른 수열을 모두 출력하는 문제이다. 수열은 비내림차순(오름차순, 같은 수 연속 허용)이어야 하며, 같은 수를 중복해서 고를 수 있다. 임의의 N개 자연수를 중복 허용하여 비내림차순 수열을 만드는 중복 조합 문제이다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 10,000보다 작거나 같다.
출력
한 줄에 하나씩, 비내림차순인 M개짜리 수열을 모두 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1 3 1 4 | 1 3 4 |
3 2 3 1 4 | 1 1 1 3 1 4 3 3 3 4 4 4 |
풀이
N개의 자연수 중 M개를 고르는 중복 조합(비내림차순, 중복 허용)을 백트래킹으로 열거한다. 정렬 후, 현재 선택한 인덱스부터 다시 탐색하도록 시작 인덱스를 유지함으로써 비내림차순 조건과 중복 허용을 동시에 만족한다.
- 입력받은 N개의 수를
Arrays.sort()로 오름차순 정렬한다. comb(d, st)재귀 함수를 호출한다.d는 현재 선택 깊이,st는 탐색 시작 인덱스이다.d == M이면 선택된 배열sel을 출력하고 반환한다.st부터 N-1까지 순회하며sel[d] = arr[i]로 선택한다.comb(d+1, i)를 호출한다. 다음 단계 시작 인덱스가i+1이 아닌i이므로 같은 수를 다시 선택할 수 있다.
핵심 아이디어: 중복 조합은 "현재 선택한 인덱스부터 다시 탐색"하는 것이 핵심이다. comb(d+1, i)에서 i를 그대로 전달함으로써 같은 원소를 반복 선택하면서도, 이전 인덱스로는 되돌아가지 않아 비내림차순 조건이 자동으로 만족된다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Day57BOJ15657N과M8오름차순조합 {
static int N, M;
static int[] arr, sel;
static StringBuilder sb;
static List<String> ans;
public static void main(String[] args) throws Exception {
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[N];
sel = new int[M];
sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
comb(0, 0);
System.out.println(sb);
br.close();
}
private static void comb(int d, int st) {
if (d == M) {
sb.append(Arrays.toString(sel).replaceAll("[\\[\\],]", "").trim()).append("\n");
return;
}
for (int i = st; i < N; i++) {
sel[d] = arr[i];
comb(d + 1, i);
}
}
}복잡도
- 시간: O(C(N+M-1, M)) — 중복 조합의 수
- 공간: O(M) — 재귀 스택 깊이 M, 선택 배열 M