[백준/BOJ] 15650번 N과 M (2) (C/C++)

백준 온라인 저지(BOJ) 15650번 N과 M (2)

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

15650번: N과 M (2)

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

 

1. 문제

N개의 수에서 M개의 숫자를 중복없이 뽑아 오름차순으로 출력 (nCm 조합)

 

2. 풀이

앞선 N과 M (1)와 유사한 방식, 즉 숫자 출력용 배열과 DFS 구조를 활용하여 풀었습니다.

https://rightbellboy.tistory.com/307

[백준/BOJ] 15649번 N과 M (1) (C/C++)

 

단, 앞선 순열 문제와는 다르게 오름차순인 수열만 출력해야 하므로

바로 앞 숫자(arr[idx - 1])보다 1 큰 수부터 combination 재귀 호출을 했습니다.

 

이렇게 수정하고 나니 visited 배열도 필요 없어져서 없앴고,

idx == 0 조건을 if문 없이 동일하게 처리하고 싶어서 idx를 1부터 8까지 활용했습니다.

 

자세한 내용은 아래 코드 참고하시길 바랍니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
15650_N과 M (2)
1112KB	0ms
*/
#include <cstdio>

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

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

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

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