[백준/BOJ] 15652번 N과 M (4) (C/C++)

백준 온라인 저지(BOJ) 15652번 N과 M (4)

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

15652번: N과 M (4)

* 사용언어 : C언어, C++

 

1. 문제

N개의 수에서 M개의 숫자를 뽑아 나열하는 모든 경우를 출력

(숫자 중복 허용, 비내림차순 수열만)

 

2. 풀이

아래 (3)번 풀이로 작성한 코드에서 약간만 수정하여 풀었습니다.

for문을 통해 재귀함수를 타는 부분(수열의 다음 자리 숫자를 지정하는 부분)에서

시작 숫자를 1부터가 아닌 직전 자리의 숫자(prev)부터 반복하도록 했습니다.

(int i = 0에서 int i = prev로 수정)

 

수열의 첫 번째 자리(idx == 0)에는 직전 숫자가 있을 수 없으니 idx != 0일 때 직전 숫자를 찾게 했습니다.

 

https://rightbellboy.tistory.com/309

[백준/BOJ] 15651번 N과 M (3) (C/C++)

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
15652_N과 M (4)
1112KB	4ms
*/
#include <cstdio>

const int LM = 8;
int arr[LM], N, M;

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

	int prev = 1;
	if (idx != 0) prev = arr[idx - 1];

	for (int i = prev; i <= N; ++i) {
		arr[idx] = i;
		permutation(idx + 1);
	}
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d %d", &N, &M);
	permutation(0);
	return 0;
}