[BOJ]15663번: N과 M(9)(c++)

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

15663번: N과 M (9)

 

 

방법 1: 각 숫자의 개수를 저장한 배열 / 중복 제거한 숫자열 만들기

#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)
{
	if (depth == M)
	{
		for (int i = 0; i < M; ++i)
		{
			cout << output[i] << ' ';
		}
		cout << '\n';

		return;
	}

	/*
		오름차순, 중복 허용X
		한번 숫자를 쓸 때마다 개수 - 1
		아직 숫자를 꺼내 쓸 수 있으면 선택 가능.
	*/
	for (int i = 0; i < N; ++i)
	{
		if (cnt[i] > 0)
		{
			--cnt[i];
			output[depth] = numbers[i];
			dfs(N, M, depth + 1);
			++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];

	for (int i = 0; i < N; ++i)
	{
		cin >> tmp[i];
	}
	
	// 오름차순 정렬
	sort(tmp, tmp + N);

	// 각 숫자의 개수를 저장한 cnt배열 만들기
	// numbers배열에 중복 제거한 숫자들 저장하기
	int num = -1;
	int idx = 0;
	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];
		}
	}

	// 중복 제거한 숫자 개수 중에서 M개 뽑기
	dfs(idx, M, 0);

	return 0;
}

 

 

방법 2: map 사용

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cmath>

using namespace std;

const int MAX = 8;
bool visited[MAX];
int numbers[MAX];
int output[MAX];
unordered_map<int, int> count_map;

/*
	만들어진 숫자열 -> 숫자로 변환하여 map에 등록.
	중복하지 않으면 출력
*/
void dfs(int N, int M, int depth, int sum)
{
	if (depth == M)
	{
		if (++count_map[sum] == 1)
		{
			for (int i = 0; i < M; ++i)
			{
				cout << output[i] << ' ';
			}
			cout << '\n';
		}

		return;
	}
	
	for (int i = 0; i < N; ++i)
	{
		if (!visited[i])
		{
			visited[i] = true;
			sum += numbers[i] * pow(10, depth);
			output[depth] = numbers[i];
			
			dfs(N, M, depth + 1, sum);
			
			sum -= numbers[i] * pow(10, depth);
			visited[i] = false;
		}
	}
}

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

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

	sort(numbers, numbers + N);

	dfs(N, M, 0, 0);

	return 0;
}

 

 

방법 1이 더 효율적이다.

왜냐면 방법 2는 만들어지는 모든 수를 map에 저장하여 카운팅 하기 때문이다.

직관적이지만 쓸데없이 저장공간을 차지하고 느리다.

 

TIP (방법 1 : 중복 제거, 중복 개수 고려)

 

중복되는 수열을 여러 번 출력하면 안되며,

문제에서 주어진 가장 중요한 조건은 이것이다.

같은 숫자가 여러번 주어진다면, 출력되는 한 줄에는 같은 숫자가 여러번 나올 수 있다 .

하지만 "출력"이 중복되면 안된다.

 

출력 기준! 중복이 있으면 안된다.

 

 

 

따라서 우리는

1. 중복을 제거한 숫자열을 만들어 이를 가지고 조합을 해야한다.

2. 써먹을 수 있는 숫자의 개수를 저장한 배열을 만든다.

 

 

이렇게! 중복을 제거한 숫자열 num[]과 1 7 은 각기 1개, 9는 2개 있다는 배열 cnt[]을 만들어준다.

 

 

1 7 9 9 를 예시로 들면, 

조합을 num[0] ~ num[2], 즉 1 7 9 의 범위에서 선택 하게 된다.

 

 

위에서 예시로 든 1 9 조합을 그림으로 표현해 보면,

두번째 dfs 호출에서는 1을 선택할 수 없다. 여분의 개수가 0 이므로

 

dfs()재귀함수 호출의 depth가 깊어질 때마다

선택한 숫자의 여분이 1씩 깎이게 되고, 여분이 없는 수는 선택할 수 없다. 

 

 

 

이어서 9 9 조합을 그림으로 표현해 보면,

9는 여분 개수가 2개나 있기 때문에, 2번째 dfs함수 호출에서도 선택할 수가 있었다

 

 

이렇게 문제의 요구사항을 충족할 수 있었다. 끝!