[BOJ] 백준 15652번 N과 M (4)

링크

https://www.acmicpc.net/problem/15652

문제

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

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

입력

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

출력

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

풀이

//백트래킹.. 
//고른 수열이 오름차순이므로 조합 combination -> 반복문 start값을 변경 
// 중복이 없는 조합인데 순열 내의 같은 값 중복은 된다. isused 필요 없음.
#include <iostream>
using namespace std;
int n, m;
int arr[10];

void solve(int cur) {
	if (cur == m) {//cur==m이면 출력 후 리턴
		for (int i = 0; i < m; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	int st = 1; // cur이 0일때 
	if (cur != 0) st = arr[cur - 1]; //재귀 들어오기전에 arr에 넣은 값이 시작값. 중복이므로 +1은 안한다.
	for (int i = st; i <= n; i++) {
		arr[cur] = i; 
		solve(cur + 1);
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	solve(0);
}

설명

📌 고른 수열이 비내림차순이므로 조합 combination -> 반복문 시작점 start값을 변경해야한다.
📌 순열 경우의 수 사이의 중복이 없는게 조합인데 순열 내의 같은 값 중복은 된다. isused 필요 없음.