글 읽기 - 2098 외판원순회문제 시간초과질문입니다..

bw2218 6년 전 0

accept 코드와 굉장히 유사한 코드인데 제 코드는 시간초과가 뜨네요!

메모이제이션까지 하고 정답도 잘 출력이 되는것 같은데 무엇이 문제일까요!

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace::std;
int N; // 도시의 수 (2<=N<=16)
int memo[16][16];
int cache[16][16];
int start = 1;
int City(int city, int state) // 외판원 순회드는 최소비용 반환 -> 마지막으로 방문한 도시, 현재상태
{

	int a = 1;
	int b = a << (city - 1);

	if (state + b == (1 << N) - 1) // 모든 도시를 방문하였으면
		return cache[city][state] = memo[city][start];
	if (cache[city][state] != -1) // cache에 해당 값이 있으면
		return cache[city][state];


	int Min = 987654321;
	for (int i = 1; i <= N; i++)
	{
		int v = (a << (i - 1));
		if (state & v || memo[city][i] == 0) // 방문 한 적이 있거나 길이 없을 경우
			continue;
		Min = min(Min, City(i, state + b) + memo[city][i]);
	}

	return cache[city][state] = Min;
}
int main(void)
{
	memset(cache, -1, sizeof(cache));
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			scanf("%d", &memo[i][j]);

	printf("%d", City(1, 0));
	





	return 0;
}

ntopia 6년 전 1

cache 배열을

cache[16][16] 으로 잡을게 아니고

cache[17][1 << 16] 으로 잡아야 제대로 돌아가겠죠.

배열 범위를 벗어나는 바람에 프로그램 상태가 이상해져서 무한루프를 도는게 아닌가 싶습니다.

bw2218 6년 전 0

그부분도 잘못되었었네요!! 감사합니다.

그런데 그렇게 수정을 해도 시간초과 오류는 나아지지가 않네요..

무엇이 문제일까요!!..

ntopia 6년 전 1

memo 배열도

memo[17][17] 로 잡으세요

bw2218 6년 전 0

감사합니다~ 배열범위 설정이 문제였군요!!

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

문제

문제

출처

ICPC

2098 외판원순회문제 시간초과질문입니다..

bw2218 6년 전 0

ntopia 6년 전 1

bw2218 6년 전 0

ntopia 6년 전 1

bw2218 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말