백준 15652번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	512MB	실버 3

---

풀이

 역시 백트래킹 문제이다. 다만 이전에 풀었던 15650번 N과 M(2)과 비슷한 문제이다. 비내림차순이라는 단어가 나와서 내림차순이 아닌 상태의 수열을 출력하라는줄 알고 순간 놀랐지만, 오름차순이라는 말을 굳이 꼬아서 쓴 것이었다. 해당 문제는 중복을 허용하기 때문에 15650번과는 다르게 반복문의 범위를 이전에 선택한 값도 다시 선택할 수 있도록 했다.

코드

#include <iostream>
#define endl '\n'
using namespace std;

int n, m;

void sol(int prev, int cnt, string output) {
	if (cnt == m) {
		cout << output << endl;
		return;
	}

	for(int i = prev; i <= n; i++) {
		sol(i, cnt + 1, output + to_string(i) + " ");
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> m;
	sol(1, 0, "");
}