#15649: N과 M(1)

백준 15649번: N과 M (1)

문제:

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력:

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

풀이:

재귀함수를 이용하는게 핵심이며 재귀함수로 한번 들어갈 때 마다 그 인덱스에 넣을 만한 알맞는 값을 찾아서 넣어야 됨. 그렇게 할려면 두개의 array를 이용하여 현재 어떤 숫자가 사용 되고 있는지 확인하고 그 숫자가 사용 중이면 넘기고 그 중에서 가장 작은 수를 현재 인덱스에 맞는 숫자를 집어 넣는 방법이다. 숫자를 집어 넣고 출력이 완료 된 후로는 가장 마지막으로 넣은 값을 0으로 바꾸고 다시 loop을 돌면서 알맞는 값을 넣는다.

🔎 이런 재귀함수는 제일 첫번째로 넣어야 할 if문에 이 재귀를 탈출 하는 조건을 적어 놓아야 된다.

코드:

#include <iostream>
using namespace std;

int n, m, c[9], a[9];

void brute_force(int index){
	if(index == m){
		for(int i = 0; i < m; i++){
			cout << a[i] << " ";
		} 
		cout << "\n";
		return;
	}
	for(int i = 1; i <= n; i++){
		if(c[i]) continue;
		a[index] = i; //현재 인덱스에 숫자를 넣음
		c[i] = 1; //사용 중인 숫자인지 기록
		brute_force(index+1);
		c[i] = 0; //사용 중이지 않은 것으로 되돌림
		a[index] = 0; //현재 인덱스 다시 비움
	}
}

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