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

이번 문제는 중복조합으로 생성된 수열 중 비내림차순에 해당하는 수열만 출력하는 문제입니다. N과 M(3) 문제와 비슷한 코드를 사용하며 다른 점은 M 길이의 수열을 출력하기 전 해당 수열이 비내림차순인지 확인하는 과정을 거친다는 점입니다.

N과 M(3)에 대한 설명은 아래 글에 있습니다.

2021.06.21 - [알고리즘] - [BOJ 15651번] N과 M (3)

[BOJ 15651번] N과 M (3)

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

#include<stdio.h>

int N, M;
int sequence[10];

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

	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) {
		final_process();
		return;
	}
	else {
		for (int i = 1; i <= N; i++) {
			sequence[depth] = i;
			back(depth + 1);
		}
	}
	return;
}

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

15652번: N과 M (4) (acmicpc.net)