[BOJ]15664번: N과 M (10)(c++)

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

15664번: N과 M (10)

 

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 8;
int numbers[MAX];
int output[MAX];
int cnt[MAX];

void dfs(int N, int M, int depth, int start)
{
	if (depth == M)
	{
		for (int i = 0; i < M; ++i)
		{
			cout << output[i] << ' ';
		}
		cout << '\n';

		return;
	}

	/* 
		비내림차순 --> 다음 숫자는 이번숫자 idx부터 조회 시작
		중복 허용X --> 한번 숫자를 쓸 때마다 개수 - 1 
		아직 숫자를 꺼내 쓸 수 있으면 선택 가능. 
	*/

	for (int i = start; i < N; ++i)
	{
		if (cnt[i] > 0)
		{
			--cnt[i];
			output[depth] = numbers[i];
			dfs(N, M, depth + 1, i);
			++cnt[i];
		}
	}

}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;
	int tmp[MAX] = {0,};
	for (int i = 0; i < N; ++i)
	{
		cin >> tmp[i];
	}

	sort(tmp, tmp + N);

	int num = -1;
	int idx = 0;

	// 각 숫자의 개수를 저장한 cnt배열 만들기 
	// numbers배열에 중복 제거한 숫자들 저장하기
	for (int i = 0; i < N; ++i)
	{
		if (num != tmp[i])
		{
			num = tmp[i];
			numbers[idx] = tmp[i];
			++cnt[idx];
			++idx;
		}
		else
		{
			++cnt[idx - 1];
		}
	}

	dfs(idx, M, 0, 0);

	return 0;
}

 

 

TIP

N과 M(9) 문제와 거의 유사하다

 

차이점은 딱 하나!

비내림차순 이라는 것. 

 

dfs()함수의 인수를 하나 더 추가해서, 

다음에 호출되는 함수는 현재 index부터 조회하도록 한다.