글 읽기 - 모든 경우의 수를 구하는 방법...

m48tank1 8년 전 0

순열을 이용해서 모든 경우의 수를 검색 후 각각의 값을 체크해서 제일 작은 값을 찾는 방법으로 구현했습니다.

재귀함수로 구현이 되어 N 값이 커지면 time out이 발생을 합니다.

모든 경우의 수를 구하는 방법이 또 없을까요?

#if 1
#include <stdio.h>

#define MAX_ARR	1001
int ARR[MAX_ARR];
int min = 0xFFFF;

int swap(int *x, int *y)
{
	int temp = *x;
	//printf("Before Swap %d %d\n", *x, *y);
	*x = *y;
	*y = temp;

	//printf("After Swap %d %d\n", *x, *y);
	return 0;
}

int Purm(int i, int size)
{
	if (i == size)
	{
		int sum = 0;

		for (int k = 0; k < size; k++)
		{
			for (int l = 0; l <= k; l++)
			{
				sum += ARR[l];
			}
			
			//printf("%d ", ARR[k]);
		}
		//printf("\n");

		if (min > sum) min = sum;
	}
	else
	{
		for (int j = i; j < size; j++)
		{
			swap(&ARR[i], &ARR[j]);
			//printf("1   %d %d\n", i, j);
			Purm(i + 1, size);
			swap(&ARR[i], &ARR[j]);
			//printf("2   %d %d\n", i, j);
		}
	}

	return 0;
}

int main()
{
	int i, N;
	//freopen("11399.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	scanf("%d\n", &N);
	
	for (i = 0; i < N; i++)
		scanf("%d ", &ARR[i]);
	//for (i = 0; i < N; i++) printf("%d ", ARR[i]);
	//printf("\n");
	Purm(0, N);

	printf("%d\n", min);
}

#endif

m48tank1 8년 전 0

바로 해결했습니다. 모든 경우의 수를 구할 필요가 없네요. ^^

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

모든 경우의 수를 구하는 방법...

m48tank1 8년 전 0

m48tank1 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말