[백준 / C언어] 15650번: N과 M (2)

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

15650번: N과 M (2)

 

난이도: solved.ac 실버 3

 

알고리즘 분류

---

백트래킹

 

접근 방법

---

뒤에 나오는 수가 앞에 나온 수보다 커야 한다

 

따라서 last라는 변수를 두었고, 뒤에 나오는 수는 last보다 더 큰 수가 나오도록 해야 한다

 

M개의 for문을 사용하는 대신 재귀 함수를 이용해 구현한다

 

 

구현

---

find라는 재귀 함수를 만들었다

 

변수 num은 현재 수열의 길이를 의미하고 last는 나열된 숫자들 중 가장 마지막에 있는 수를 의미한다

 

Ex. 1 4 5까지 나열되었다고 할 때

num = 3 (1, 4, 5로 숫자가 3개이므로)

last = 5 (가장 마지막 숫자 = 5)

 

나열할 숫자를 last부터 시작하도록 하고 숫자를 arr에 집어넣으면 find를 재귀호출한다

 

find의 매개변수 num과 last는 숫자가 하나 더 늘었으므로 num은 num + 1로 넘겨주고, 넣었던 숫자 보다 1 큰 값을 last로 넘겨준다

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

void find(int num, int last);
int N, M;
int arr[8];

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

void find(int num, int last) {
	int i;
	if (num == M) {
		for (i = 0; i < M; i++)
			printf("%d ", arr[i] + 1);
		printf("\n");
	}
	else {
		for (i = last; i < N; i++) {
			arr[num] = i;
			find(num + 1, i + 1);
		}
	}
}