백준 15650번 C++ 풀이

문제

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

 

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

---

풀이

이 문제를 무작정 중첩반복문으로 풀기에는 어려워보인다. 중첩반복문을 쓰게되면 시간복잡도의 문제도 생기지만, 그 전에 몇번 중첩해야할지가 애매해진다. 숫자를 M개를 선택해야하는데, 이는 단순하게 생각해서 M중첩 반복문이 필요하다는 뜻이 될테니 말이다. 따라서 반복문만 사용하는 것이 아닌, 재귀함수와 섞어, 어떤 숫자를 선택했을때, 그 뒤의 숫자부터 다시 탐색하도록 작성하였다. 그러기 위해 제일 최근에 선택한 숫자가 무엇인지, 지금 몇개를 선택했는지를 재귀하면서 넘겨주고, 항상 이전에 선택한 숫자보다 더 큰 숫자부터 다시 탐색을 하는 방식을 선택하였다. 답을 출력하기 용이하도록 답을 문자열로 구성해나갔다.

 

이런 류의 문제를 백트래킹 알고리즘이라고 한다. 그런데 아직 백트래킹을 정확히 뭐라고 설명해야할지 잘 모르겠다. 기본골자는 브루트포스인데, 여기서 더 탐색해봤자 해가 아니거나 최적해가 아닌게 자명하다면 더 탐색하지 않는 방식으로 탐색의 숫자를 줄여나가면서도, 완전탐색의 강력함을 챙기는 알고리즘인거 같다. 솔직히 아직 감이 잘 잡히진 않는데, 내 풀이를 백트래킹에 끼워넣어보자면, 입력이 8 4이라고 해보자. 우리는 1~8에서 4개를 뽑아야 한다. 그리고 우리는 2와 4를 골라둔 상태이다. 여기서 우리는 1~4는 골라봤자 답이 아니라는걸 알 수 있다. 중복이어선 안되고, 오름차순으로 정렬되어야 하는데, 2와 4 다음에 1이 올수도 없을 뿐더러, 1 2 4 @ 라는 답은 이전에 1을 고른 후 재귀했을때 이미 찾았을 것이기 때문이다. 우리는 이전에 선택한 값을 재귀함수의 인자로 넘겨줬기 때문에 이 값보다 작거나 같은 값은 답이 될 수 없다는 것을 자명하게 알 수 있기 때문에 탐색하지 않는 것이다.

 

솔직히 백트래킹에 대해서 몇문장 쓰고, 내 문제가 어디에서 백트래킹을 쓴걸까하고 끼워맞추면서 써본거다. 맞을수도 있고 아닐수도 있다.

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n, m;

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

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

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