[알고리즘/문제풀이/BOJ 15650번] N과 M (2)

이번 문제는 BOJ 15649번 N과 M(1)과 동일한 문제입니다. 다만, 오름차순의 수열만을 출력해야하므로 재귀함수의 탈출조건에서 수열을 출력하기 전에 수열이 오름차순으로 정렬되어 있는지 확인하는 과정을 추가하여야 합니다.

BOJ 15649번에 대한 설명은 하단의 링크에서 확인부탁드립니다.

https://ark-hive.tistory.com/14

작성한 코드는 다음과 같습니다.

#include<stdio.h>

int N, M;
int sequence[10];
int check[10];

//back tracking은 모든 경우를 탐색할 때 사용하는 기법입니다.
//기능 특성상 재귀함수 형태로 구현됩니다. 
void final_process(){ 
	for (int i = 0; i < M-1; i++) {
		printf("%d ", sequence[i]); 
	}
	printf("%d\n", sequence[M - 1]); 
} 

void back(int depth) {
	if (depth == M) {

		for (int i = 0; i < M - 1; i++) {
			if (sequence[i] > sequence[i + 1]) {
				return;
			}
		}

		final_process();
		return; 
	} 
	else {
		for (int i = 1; i <= N; i++) {
			if (check[i] == 0) {
				sequence[depth] = i;
				check[i] = 1;
				back(depth + 1);
				check[i] = 0;
			} else if (check[i] == 1) {
				continue; 
			} 
		} 
	} 
	return; 
} 

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

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