BOJ 15663 : N과 M (9)

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/15663

 

 

N과 M의 응용 버전이다.

N과 M (5)에서 visit 배열을 이용해 번호를 사용했는지 체크했다면, 

이제는 visit을 counting해서 가능한 수까지 사용하도록 바꾸면 된다.

 

예제 입력 2를 보자.

4 2
9 7 9 1

 

9가 2개, 7이 1개, 1이 1개 있다.

 

즉, 9는 최대 2번까지 visit으로 카운팅 할 수 있다.

따라서 possible 배열을 만들어서, possible[9] = 2를 저장해두자.

9를 사용하였다면, visit[9]++가 되고, 1 = visit[9] != possible[9] = 2가 되므로, 9를 한번 더 사용할 수 있게 된다.

 

이때, 입력값 N은 4가 되지만 위와 같이 사용하려면 N = 3으로 변경해야 한다.

중복된 숫자를 제외하고 남은 숫자를 input에 다시 넣어서 기존 코드를 재사용하도록 변경하면 된다.

int count = 1; /* 기존 코드 index가 1부터 시작해서 1로 두었다. */
for (int i = 1; i <= N; i++)
{
	int in;
	scanf("%d", &in);
		
	if (possible[in] == 0) input[count++] = in; /* possible을 보고 input에 새로 넣자 */
		
	possible[in]++; /* 가능한 사용 횟수 count */
}

N = count - 1; /* N을 변경 */

 

최종 코드는 아래와 같다.

가능한 번호의 수가 10000이므로 possible을 넉넉하게 잡아줘야 한다.

#include <stdio.h>

int N, M;

int list[10];
int visit[10];
int possible[10000 + 100]; /* 가능한 번호의 수 10000 */
int input[10]; /* input 저장 */

void outputList()
{
	for (int i = 0; i < M;i++) printf("%d ", list[i]);
	putchar('\n');
}

void DFS(int L)
{
	if (L == M)
	{
		outputList();
		return;
	}

	for (int i = 1; i <= N;i++)
	{
		if (visit[i] == possible[input[i]]) continue;

		list[L] = input[i]; /* i 대신 input[i] */

		visit[i]++;
		DFS(L + 1);
		visit[i]--;
	}
}

int main(void)
{
	scanf("%d %d", &N, &M);

	int count = 1;
	for (int i = 1; i <= N; i++)
	{
		int in;
		scanf("%d", &in);
		
		if (possible[in] == 0) input[count++] = in;
		
		possible[in]++;
	}

	N = count - 1;

	/* 정렬 */
	for (int i = 1; i <= N - 1; i++)
	{
		for (int k = i + 1; k <= N; k++)
		{
			if (input[i] > input[k])
			{
				int tmp = input[i];
				input[i] = input[k];
				input[k] = tmp;
			}
		}
	}
	
	DFS(0);

	return 0;
}