[백준 15649] N과 M (1)

개인적으로 백트래킹이나 브루트포스나 큰 차이가 없다고 생각한다.

그래도 백트래킹이라고 하면, 보통 재귀 함수를 통해 모든 경우의 수를 탐색하는 것을 말한다.

나중에 가지치기(pruning)라는 기법으로 탐색 시간을 줄일 수 있다.

기법이라고 해서 좀 어려워보이는데.. 그냥 조건문을 통해 더 탐색을 할 것인지 결정해주는 거라고 보면 된다.

 

N과 M 시리즈는 별 거 없다. 백트래킹으로 문제에서 원하는 조건만 잘 지켜주면 해결 가능하다.

코드 재사용을 통해 어떤 조건을 어떻게 바꿔야 하는지 훈련하면 좋을 것 같다.

 

#include <bits/stdc++.h>
using namespace std;

int N, M;
bool isTrue[9]; // 이미 뽑힌 숫자인지 ?
int ans[9]; // 답 저장

// cnt : 몇 개가 뽑혔는지
void recur(int cnt) {
	// 원하는 개수가 다 뽑혔다면 답 출력
	if (cnt == M) { 
		for (int i = 0; i < M; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}
    
	// 1 ~ N까지 돌면서 안뽑힌 숫자를 뽑고 다음 재귀함수 호출
	for (int i = 1; i <= N; ++i) {
		if (isTrue[i]) continue;

		isTrue[i] = true;
		ans[cnt] = i;
		recur(cnt + 1);
		// 호출이 끝나면 뽑힌 숫자를 놓아준다.
		isTrue[i] = false;
	}
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> N >> M;

	recur(0);
	
	return 0;
}