알고리즘 :: 백준 :: Bruteforce :: 15649 :: N과 M (1)

문제

문제링크

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

문제접근

• <algorithm>헤더의 next_permutation() 함수를 쓰면 간단하게 풀 수 있는 문제지만, 만일 STL을 사용할 수 없는 경우라면 이 문제를 어떻게 풀 수 있을지 생각해보자.
• N과 M의 범위가 8까지로 매우 작기 때문에 bruteforce를 사용해보자. 재귀적인 관점에서 순서를 만들어가보자.
• 재귀적 bruteforce의 핵심알고리즘은 고정, 실행 그리고 해제다.
• 재귀를 돌면서 결과 배열의 idx번 위치에 1부터 8까지의 숫자를 넣고 다음 재귀를 돌리고 다시 빼는 과정을 반복한다.

코드

#include <iostream>

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

void solve(int idx) {
	// m개를 선택했다면, 결과를 출력한다.
	if (idx == m) {
		for (int i = 0; i < m; ++i) printf("%d ", a[i]);
		printf("\n");
		return;
	}
    	// 1부터 n까지의 수를 '고정', '실행', '해제'한다.
	for (int i = 1; i <= n; ++i) {
		if (c[i]) continue;
		a[idx] = i;
		c[i] = 1;
		solve(idx + 1);
		c[i] = 0;
		a[idx] = 0;
	}
}

int main() {
	scanf("%d %d", &n, &m);
	solve(0);
}

결과