알고리즘 :: 백준 :: Bruteforce :: 15650 :: N과 M (3)

문제

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

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

문제접근

• 숫자에 중복을 허용한 경우에는 어떻게 문제를 풀어야 할까?
• 중복을 허용했기 때문에 숫자 등장을 check할 필요가 없다.
• 단, 이 문제는 '선택'적 관점으로는 풀 수 없다.
  선택하지 않는 경우에 대해 무한 loop를 돌기 때문이다.
  (혹시 이 문제를 선택적 관점으로 풀 수 있다면 피드백 부탁드리겠습니다.)

코드

#include <iostream>
using namespace std;
int n, m, a[7];
void solve(int idx) {
	if (idx == m) {
		for (int i = 0; i < m; ++i) cout << a[i] << ' '; cout << '\n';
		return;
	}
	for (int i = 1; i <= n; ++i) {
		a[idx] = i;	// check 안함.
		solve(idx + 1);	// 바로 다음 자리로 넘어감.
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	solve(0);
}

결과