[백준] 15650번 N과 M C++ 문제풀이

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

15650번: N과 M (2)

문제 풀이

1 ~ N 중의 수 중에 M개를 오름차순으로 출력하는 문제이다.

문제를 보자마자 백트래킹을 이용해 수열을 탐색해야 한다고 생각해 DFS를 통해 문제의 조건을 만족하는 수열만 출력했다.. 

bool 타입의 num 배열을 만들어 true인 인덱스의 수만 출력했다.

주의할 점은 dfs를 진행할 때 이전에 true가 된 수의 다음 수부터 탐색을 이어가야 한다는 점이다.

소스 코드

#include <iostream>
using namespace std;

int M, N;
bool num[10] = { false };

void dfs(int start, int cnt) {
	if (cnt == N) {
		for (int i = 1; i < 10; i++) {
			if (num[i] == true) {
				cout << i << " ";
			}
		}
		cout << '\n';
	}
	else {
		for (int i = start; i <= M; i++) {
			num[i] = true;
			dfs(i + 1, cnt + 1);
			num[i] = false;
		}
	}
}

int main() {
	cin >> M >> N;

	dfs(1, 0);
}