[백준/C++] 백트래킹 N과 M (2) - 15650번

백준 15650번  N과 M(2) 풀이

 

N과 M (2) 설명

백트래킹은 완전 탐색과 비슷하게 하나하나 다 경우를 따져보는 알고리즘이다.

일반적으로 다 따져보기 때문에 경우의 수가 큰 문제는 적용할 수 없다. 

보통 재귀함수를 섞어서 쓰기 때문에 선행적으로 재귀에 대한 이해가 필요하다. 

 

이 문제에서 볼 때 조건은 아래와 같이 2가지이다.

• 조건 1. N개의 자연수를 M 개씩 나열한다.
• 조건 2. 오름차순으로 나열한다. 

조건 1을 따져보면 n개와 m개를 입력받고 재귀함수 안에서 m개의 조건을 충족하면 출력한다.

bool issu[9];
int list[9];
int num = 0;
int n, m;

void func(int a) {
	if (num == m) {
		for (int i = 1; i <= n; i++) {
			if (issu[i] == 1) {
				cout << i << " ";
			}
		}
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (a > i) continue;
		else if(issu[i] != 1){
			issu[i] = 1;
			num++;
			func(i);
			issu[i] = 0;
			num--;
		}
	}

}

 

또한, 조건 2를 적용해보자면 위 재귀함수 중 n개의 자연수 중 아직 쓰지 않은 수를 체크하고 그 수가 전에 썼던 수보다 크면 적용, 작으면 패스하는 식으로 적용했다.

함수에 들어가는 인자 a는 바로 직전에 썼던 수를 넣어준 것이다. 

인자가 들어가기전 issu, num을 추가해주고 func에 들어가는 구조이다. 

 

여기서 조심할 점은 n개의 수를 쓸 때 내가 쓰지 않은 수를 조건으로 따져봐야한다는 것이다.

issu[i] != 1이 바로 그 조건인 것이다.

 

이렇게 적용하면 쉽게 문제를 풀 수 있다. 

#include<iostream>
#include<algorithm>

using namespace std;
bool issu[9];
int list[9];
int num = 0;
int n, m;

void func(int a) {
	if (num == m) {
		for (int i = 1; i <= n; i++) {
			if (issu[i] == 1) {
				cout << i << " ";
			}
		}
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (a > i) continue;
		else if(issu[i] != 1){
			issu[i] = 1;
			num++;
			func(i);
			issu[i] = 0;
			num--;
		}
	}

}
int main() {
	
	
	cin >> n >> m;
	
	func(0);
}