[BOJ] 15649번 N과 M (1) (C++)

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

15649번: N과 M (1)

 

#include <iostream>
using namespace std;

int n, m;
int arr[9];
bool isused[9];

void func(int k) {
	if (k == m + 1) {
		for (int i = 1; i <= m; i++)
			cout << arr[i] << " ";
		cout << "\n";
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (!isused[i]) {
				isused[i] = true;
				arr[k] = i;
				func(k + 1);
				isused[i] = false;
			}
		}
	}
}

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

arr은 수열을 담을 배열, isused는 특정 수가 쓰였는지를 true 혹은 false로 나타내는 배열이다. 

3, 2가 들어있는 상태라면 arr[0]=3, arr[1]=2이고 1과 쓰이는 아직 쓰이지 않았는데 2와 3은 쓰였으므로 isused[1]=false, isused[2]=true, isused[3]=true, isused[4]=false이다.

 

func(k)는 현재 k개까지 수를 택한 상황에서 arr[k]를 정하는 함수이다.

맨 처음 func(1)을 호출하고 func(1)은 arr[1]을 정한 후에 func(2)를 호출한다. 

 

k=m+1이 되었을 때 m개를 모두 택했으니 수열을 출력한 후 함수를 종료한다.

k가 m+1이 아니라면 n까지의 수를 차례로 확인하며 아직 쓰이지 않은 수를 찾아낸다.

 

!isused[i]는 arr[k]=i, isused[i]=true로 만든 후 func(k+1)을 호출한다. 

isused[i]=false arr[k]=i로 둔 상태에서 func(k+1)에 들어갔다가 모든 과정을 끝낸 후이므로 isused[i]=false로 되돌려 수 i가 사용되고 있지 않음을 명시한다. 단, 현재 값이 i인 arr[k]는 굳이 0과 같은 값으로 변경할 필요가 없는데 어차피 자연스럽게 다른 값으로 덮일 예정이라 그런 것이다.