BOJ 15652 - N과 M (4)

문제 링크

문제#

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 $K$인 수열 $A$가 $A_1 \le A_2 \le \cdots \le A_{K-1} \le A_K$를 만족하면, 비내림차순이라고 한다.

입력#

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력#

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이#

중복은 허용하지만 수열은 비내림차순이어야 한다. 그래서 다음 자리에서는 현재 선택한 수보다 작아지는 후보만 막으면 된다.

코드는 재귀 함수에 다음 후보의 시작값을 함께 넘긴다. 현재 자리에서 i를 골랐다면 다음 자리도 i부터 탐색하게 만들어 같은 수는 다시 쓸 수 있고, 더 작은 수로 돌아가는 경우는 사라진다. 15650과의 차이는 다음 시작점을 i + 1이 아니라 i로 넘긴다는 점이다.

코드#

#include <iostream>
using namespace std;
 
int n, m;
int arr[8];
 
void dfs(int depth, int start) {
 
	if (m == depth) {
		for (int i = 0; i < m; i++) {
 
			cout << arr[i] << " ";
		}
		cout << '\n';
		return;
	}
 
	for (int i = start; i <= n; i++) {
		arr[depth] = i;
		dfs(depth + 1, i);
	}
}
 
void solve() {
 
	cin >> n >> m;
	dfs(0, 1);
}
 
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	solve();
 
    return 0;
}

복잡도#

• 시간 복잡도: 비내림차순 길이 $M$ 수열을 모두 출력하므로 $O(\binom{N + M - 1}{M} \cdot M)$이다.
• 공간 복잡도: 현재 수열과 재귀 스택을 저장하므로 $O(M)$이다.

마무리#

중복 허용과 비내림차순 조건은 시작 후보를 그대로 넘기는 방식으로 함께 처리할 수 있다. 현재 수보다 작은 수를 다시 보지 않으면 모든 수열이 자연스럽게 정렬된 상태로 나온다.