N 과 M 4

문제 링크

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 같은 숫자를 여러번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다. ( $a_1\le a_2\le a_3\le a_4...$을 만족 )

N 과 M 2 문제와 N 과 M 3 합성으로 볼 수 있다. 숫자 사용 여부를 확인하는 조건문은 삭제하고 이전 숫자와의 크기 비교 조건문을 삽입해 해결 할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> ch/*숫자 사용 여부*/, arr/*완성된 수열*/;
int n, m;
void r(int p) {
	if(p > m) { // 끝까지 탐색한 경우
		for(int i=1;i<=m;i++) {
			cout << arr[i] << " ";
		}
		cout << "\n";
		return; // 지금까지 저장된 문자열 출력하고 탐색 종료
	}
	for(int i=1;i<=n;i++) {	
		if(p > 1 && arr[p - 1] > i) continue; // 현재 숫자를 삽입했을 때 내림차순이 되면 탐색 생략
		arr[p] = i; // 현재 위치에 i라는 숫자 사용
		r(p + 1); // 다음 위치 탐색		
	}
}
int main() {
	cin >> n >> m;
	ch = vector<int>(n + 1); arr = vector<int>(m + 1);
	r(1);
	return 0;
}