[백준 / C언어] 15649번: N과 M (1)

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

15649번: N과 M (1)

 

난이도: solved.ac 실버 3

 

 

1부터 N까지의 숫자에서 M개를 중복없이 골라 각기 다른 순서로 섞어 나열하는 순열을 만들어내는 문제다

 

이는 DFS를 활용한 백트래킹으로 해결할 수 있다

 

우선 출력할 숫자는 배열 arr에 담아두었고

 

배열 used에는 각 인덱스에 해당하는 숫자가 배열 arr에 저장되었다면 1, 저장되지 않았다면 0을 담았다

 

그리고 idx가 M이 되면 배열 arr에 저장했던 수를 출력한다

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int arr[9];
int used[9];
int N, M;

int main() {
	scanf("%d %d", &N, &M);
	backtracking(0);
	return 0;
}

int backtracking(int idx) {
	if (idx == M) {
		for (int i = 0; i < M; i++)
			printf("%d ", arr[i]);
		printf("\n");
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (used[i] == 0) {
			arr[idx] = i;
			used[i] = 1;
			backtracking(idx + 1);
			used[i] = 0;
		}
	}
}