BOJ 15665 : N과 M (11)

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/15665

 

 

같은 수를 여러번 골라도 되기 때문에 중복되는 입력은 큰 의미가 없다.

중복되지 않은 총 수를 count하여 N을 바꾸자.

이때, N과 M (10)과 달리, possible은 중복을 체크하는 용도로만 사용한다.

int count = 1;
for (int i = 1; i <= N; i++)
{
	int in;
	scanf("%d", &in);

	if (possible[in] == 0) input[count++] = in;
}

N = count - 1;

 

N이 변경되었으므로, visit관련 코드는 모두 필요가 없다.

#include <stdio.h>

int N, M;

int list[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++)
	{
		list[L] = input[i]; /* i 대신 input[i] */
		DFS(L + 1);
	}
}

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] = 1;
		}
	}

	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;
}