ShaShaKa Dev Note

N과 M (2)

28 October 2019

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

이번은 백트래킹 입문 문제 2를 풀어보도록 하겠습니다.

#include<stdio.h>

static int N, M;
int* arr;
int visit[9] = { 0 };
void resolve(int start, int count);

int main(void) {

	scanf("%d %d", &N, &M);
	arr = new int[M];
	resolve(1,0);
}

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

	for (int i = start; i <= N; i++)
	{
		if (visit[i] == 0)
		{
			visit[i] = 1;
			arr[count] = i;
			resolve(i, count+1);
			visit[i] = 0;
		}
	}
}

1부터 N까지의 숫자중 M개로 만들 수 있는 조합을 구하는 문제입니다.
수학에서 배웠던 nCm의 문제로 생각할 수 있습니다.
예를 들어,1~4까지 2개를 고르는 문제를 생각해봅시다.
가장 처음 1을 고르면, 2,3,4의 세개의 조합을 고를 수 있습니다.
그 다음 2를 골랐을 때는 이미 1과 2의 조합은 있으므로 3,4와 조합을 할 수 있습니다.
그 다음 3을 고른 경우는 (1,3),(2,3)의 조합은 존재하므로, 4와의 조합만 가능하게 됩니다.
항상 시작 숫자보다 큰 숫자로만 진행을 하면 조합을 오름차순으로 출력할 수 있다는 것을 알 수 있습니다.
따라서, 위와 같이 재귀를 활용해 그대로 진행해주도록 합니다.