BOJ - 15649번_N과 M (1)

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

  • 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 출력한다.
  • 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

백트래킹을 이용한다.

예시로 N=4, M=3 일 때의 동작 과정을 보며 이해해보자.

  1. func(0)을 호출하자 arr[0]=1, check[1]=1이 되고 func(1)을 호출한다.
  2. func(1)을 호출하자 arr[1]=2, check[2]=1이 되고 func(2)을 호출한다.
  3. func(2)을 호출하자 arr[2]=3, check[3]=1이 되고 func(3)을 호출한다.
  4. func(3)을 호출하면 현재의 arr(값: 123)를 출력하고 return을 만나 돌아간다.
  5. func(2)가 진행중이며 check[3]=0이 된다.
  6. for문을 마저 돌면 i=4이므로, arr[3]=4, check[4]=1이 되고 다시 func(3)을 호출한다.
  7. func(3)가 호출되자 현재의 arr(값: 124)를 출력하고 return을 만나 돌아간다.


소스코드

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

int N, M;
int arr[10];
bool check[10];

void func(int num) {
	if(num==M) {
		for(int i=0; i<M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	for(int i=1; i<=N; i++) {
		if(!check[i]) {
			arr[num] = i;
			check[i] = 1;
			func(num+1);
			check[i] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	func(0);
}