[C++] 백준 15652: N과 M (4)

문제

[C++] 백준 15652: N과 M (4) SILVER 3
https://www.acmicpc.net/problem/15652

 

---

 

접근 방법

백준 15652번은 1부터 N까지의 자연수 중에서 M개를 고르는 경우를 출력하는 문제인데,

• 비내림차순(오름차순+중복 허용)
• 같은 수를 여러 번 골라도 됨

이라는 점이 15650번(중복 허용 X)과 다르다.

https://xeungcoding.tistory.com/87

[C++] 백준 15650: N과 M (2)

 

 

즉, 수열이 항상 a1 ≤ a2 ≤ a3 ≤ ... ≤ aM 형태가 되도록 만들어야 하고, 1 1 2, 2 2 2 같은 경우도 허용된다.

그래서 백트래킹을 할 때,

• start부터 n까지 반복하면서 숫자를 고르고
• 다음 재귀 호출에서도 start를 그대로 i로 유지해서 같은 숫자를 다시 고를 수 있게 구현했다.

for (int i = start; i <= n; i++)
{
    picked.push_back(i);
    backTracking(i, depth + 1); // i+1이 아니라 i!
    picked.pop_back();
}

 

이렇게 하면

• start보다 작은 수는 다시 선택되지 않으니 내림차순이 나오지 않고
• 같은 숫자를 여러 번 선택할 수 있으니 중복 선택이 허용된다.

 

구현 시 주의할 점

• 15650과의 차이점은 재귀 호출 부분에서 backTracking(i + 1, depth + 1)가 아닌
  backTracking(i, depth + 1) 라는 것.
  이 한 줄 차이로 “중복 조합”이 된다.
• depth == m일 때 picked에 쌓인 값을 그대로 출력하면 되고,
  출력 후에는 반드시 return으로 재귀를 종료해야 한다.
• 백트래킹 패턴 그대로
  • push_back → 재귀 → pop_back
    순서를 지켜야 상태가 꼬이지 않는다.

 

---

 

코드

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<int> picked;

void backTracking(int start, int depth)
{
	if (depth == m)
	{
		for (int i = 0; i < picked.size(); i++)
			cout << picked[i] << ' ';
		cout << '\n';

		return;
	}
	for (int i = start; i <= n; i++)
	{
		picked.push_back(i);
		backTracking(i, depth + 1);
		picked.pop_back();
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	backTracking(1, 0);

	return 0;
}