알고리즘 :: 백준 :: Bruteforce :: 15652 :: N과 M (4)

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

문제접근

• 숫자에 중복을 허용한 오름차순은 오름차순 코드에서 딱 한 부분만 변경해주면 구현할 수 있다.
• 기존에는 이번 loop에서 숫자 i를 넣었다면 다음 loop에서는 숫자 i + 1부터 사용할 수 있었다면, 이제는 i부터 사용할 수 있도록 하면 된다.

코드

순서를 고려한 코드

#include <iostream>
using namespace std;
int n, m, a[8];
void solve(int idx, int num) {
	if (idx == m) {
		for (int i = 0; i < m; ++i) cout << a[i] << ' '; cout << '\n';
		return;
	}
	for (int i = num; i <= n; ++i) {
		a[idx] = i;
		solve(idx + 1, i);	// i + 1이면 오름차순, i니까 비내림차순.
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	solve(0, 1);
}

선택을 고려한 코드

#include <iostream>
using namespace std;
int n, m, a[8];
void solve(int num, int cnt) {
	if (cnt == m) {
		for (int i = 0; i < m; ++i) cout << a[i] << ' '; cout << '\n';
		return;
	}
	if (num > n) return;
	a[cnt] = num;
	solve(num, cnt + 1);	// num을 선택하는 경우
	solve(num + 1, cnt);	// num을 선택하지 않는 경우
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	solve(1, 0);
}

결과