글 읽기 - 채점 50%에서 틀렸다고 뜹니다.ㅜ

ychooni 7년 전 0

permutation 재귀로 구하면서

각각의 모든 경우의 수를 배열 a에 저장하고,

(n값이 4이면 배열 a에는 1 2 3 4 를 저장)

n+1번째 인덱스(a[n])에 a[0] 값을 넣어서

예를 들면 1 2 3 4 1 이런식이 되도록 만든다음에

calc() 에서 각각의 순회의 결과를 계산해서 최소값을 ans에 저장하는 식으로 구했는데요,

permutation의 결과는 다 잘나와서 전체탐색은 될것으로 생각됩니다만,

채점 50%정도에서 틀렸다고 뜨네요..ㅜ

#include <stdio.h>

int n, a[11], w[11][11], ans=10000000;

int calc()
{
	int i, sum=0;
	a[n] = a[0];
	for(i=0; i<=n; i++) {
		sum += w[a[i]][a[i+1]];
	}
	return sum;
}

void swap_se(int k)
{
	int i, tmp = a[k];
	for(i=k+1; i<n; i++)
		a[i-1] = a[i];
	a[i-1] = tmp;
}

void permutation(int k) 
{
	int i, j;
	if(k == n-2) {
		int tmp = calc();
		if(ans > tmp)
			ans = tmp;
	
		tmp = a[k];
		a[k] = a[n-1];
		a[n-1] = tmp;
		
		tmp = calc();
		if(ans > tmp)
			ans = tmp;
		
		return ;
	}
	for(i=k; i<n; i++) {
		int t[10];
		for(j=0; j<n; j++)
			t[j] = a[j];
		permutation(k+1);
		for(j=0; j<n; j++)
			a[j] = t[j];
		swap_se(k);
	}
}

int main()
{
	int i, j;
	scanf("%d", &n);
	
	for(i=1; i<=n; i++) {
		a[i-1] = i;
		for(j=1; j<=n; j++) 
			scanf("%d", &w[i][j]);
	}
	
	for(i=0; i<n; i++) {
		int t[10];
		for(j=0; j<n; j++)
			t[j] = a[j];
		permutation(1);
		for(j=0; j<n; j++)
			a[j] = t[j];
		swap_se(0);	
	}
	
	printf("%d\n", ans);
	return 0;
}		

f52985 7년 전 1

w[i][j]=0인 경우는 i에서 j로 가는 길이 없는 경우입니다.

ychooni 7년 전 0

그것까지 처리 했는데도 틀렸다고 나오네요..

프린트 하면 모든 경우의 수는 다 찍히는데 말입니다..ㅜㅜ

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

문제

문제

출처

ICPC

채점 50%에서 틀렸다고 뜹니다.ㅜ

ychooni 7년 전 0

f52985 7년 전 1

ychooni 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말