문제
1부터 N까지의 자연수 중에서 M개를 선택하는 문제다. N과 M (1)과 달리, 고른 수열은 오름차순이어야 한다. 즉, 같은 수를 두 번 이상 고를 수 없고, 고른 수열의 순서가 오름차순인 경우만 출력한다 (조합).
입력
- 첫째 줄: N, M (1 ≤ M ≤ N ≤ 8)
출력
가능한 모든 오름차순 수열을 사전 순으로 출력 (한 줄에 하나씩)
예제
| 입력 | 출력 |
|---|---|
3 1 | 1 2 3 |
4 2 | 1 2 1 3 1 4 2 3 2 4 3 4 |
풀이
DFS(백트래킹)로 오름차순 조합을 생성한다. N과 M (1)의 순열과 달리, 재귀 호출 시 시작 인덱스를 i + 1로 넘겨 항상 이전보다 큰 숫자만 선택하도록 제한한다.
dfs(at, depth)함수에서at은 다음 탐색 시작 숫자,depth는 현재까지 선택한 수의 개수다.depth == M이면 결과 배열을 출력하고 반환한다.at부터 N까지 순회하며 현재 깊이에 숫자를 저장하고dfs(i + 1, depth + 1)을 호출한다.- 시작 인덱스를
i + 1로 넘기므로 항상 오름차순이 보장된다.
핵심 아이디어: 방문 배열 없이 시작 인덱스 at을 재귀 호출마다 i + 1로 증가시키는 것만으로 오름차순 조합을 구현한다. N과 M (1)은 순열(visit 배열 사용)이고, 이 문제는 조합(시작 인덱스 전달)이라는 점이 핵심 차이다.
코드
package com.ssafy.an.day049;
import java.util.Scanner;
public class Day43BOJ15650N과M2DFS연습 { // 15650 N과 M 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];
// 1 포함
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;
} // 1 ~ N포함 까지
for (int i = at; i <= N; i++) {
arr[depth] = i;
dfs(i + 1, depth + 1);
}
} // 구선생님.. 왜 제껀 틀리나요..
}복잡도
- 시간: O(C(N, M)) — N개 중 M개를 고르는 조합 수
- 공간: O(M) — 재귀 호출 스택 깊이와 결과 배열