BOJ 15651 - N과 M (3)

문제 링크

문제#

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력#

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

출력#

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

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

풀이#

같은 수를 여러 번 골라도 되므로 visited 배열이 필요 없다. 깊이마다 1부터 N까지를 모두 시도하고, 길이가 M이 되면 현재 수열을 출력하면 된다.

즉 재귀 트리의 각 레벨에서 선택지가 항상 N개인 중복 순열 문제다. 조건이 가장 단순한 형태라서 백트래킹의 기본 구조가 그대로 드러난다.

코드#

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

복잡도#

• 시간 복잡도: 중복을 허용한 길이 $M$ 수열을 모두 출력하므로 $O(N^M \cdot M)$이다.
• 공간 복잡도: 현재 수열과 재귀 스택을 저장하므로 $O(M)$이다.

마무리#

중복 선택이 허용되면 방문 상태를 관리할 필요가 없다. 각 자리에서 1부터 $N$까지를 모두 다시 시도하면 중복 순열 전체가 만들어진다.