글 읽기 - [C] 시간초과가 납니다...(56%)

vect_r 2년 전 0

50% 언저리에서 시간초과가 발생하는 것으로 보아서

무한루프가 있는 것 같은데 어떻게 수정해야할까요?

-올린 코드 중에서 위의 것은 return을 받지 않고, dp(temp 배열)에 값을 저장해서 답을 구하는 방식입니다. (시간초과)

==위 코드에서 dp(temp 배열)은 temp[a][b] = c: 현재 a이고, b를 경유한 최소 비용 c 입니다.

-올린 코드 중에서 아래의 것은 dp(temp 배열)을 이용해 return을 받는 방식으로 답을 구하였습니다. (맞았습니다.)

==아래 코드에서 dp(temp 배열)은 temp[a][b] = c: 현재 a이고, b를 경유한 상황에서 아직 경유하지 못한 모든 노드를 경유하였을 때의 최소 비용 c 입니다.

// 코드1 (시간초과)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N = 0, result = 1000000000, bitMaskN = 0;
int input[20][20] = { 0 };
int temp[20][1 << 16] = { 0 };

void TSP(int cPos, int mask);

int main(void) {
	(void)scanf("%d", &N);
	for (int i = 0; i < N; i++)
		for (int k = 0; k < N; k++)
			(void)scanf("%d", &input[i][k]);

	bitMaskN = (1 << N) - 1;

	TSP(0, 1);
	for (int i = 1; i < N; i++)
		if (temp[i][bitMaskN] != 0 && input[i][0] != 0)
			result = result <= temp[i][bitMaskN] + input[i][0] ? result : temp[i][bitMaskN] + input[i][0];

	printf("%d", result);
	return 0;
}

void TSP(int cPos, int mask) {
	if (mask >= bitMaskN) return;

	for (int i = 0; i < N; i++)
		if (input[cPos][i] != 0 && (mask & (1 << i)) == 0)
			if (temp[i][mask | (1 << i)] == 0 || temp[i][mask | (1 << i)] > temp[cPos][mask] + input[cPos][i]) {
				temp[i][mask | (1 << i)] = temp[cPos][mask] + input[cPos][i];
				TSP(i, mask | (1 << i));
			}

	return;
}


//////////////////////////////////////////////////////////////////
// 코드 2 (맞았습니다.)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N = 0, result = 1000000000, bitMaskN = 0;
int input[20][20] = { 0 };
int temp[20][1 << 16] = { 0 };

int TSP(int cPos, int mask);
int getMin(int first, int last);

int main(void) {
	(void)scanf("%d", &N);
	for (int i = 0; i < N; i++)
		for (int k = 0; k < N; k++)
			(void)scanf("%d", &input[i][k]);

	bitMaskN = (1 << N) - 1;
	for (int i = 0; i < N; i++)
		for (int k = 0; k <= bitMaskN; k++)
			temp[i][k] = 1000000000;

	printf("%d", TSP(0, 1));
	return 0;
}

int TSP(int cPos, int mask) {
	if (mask >= bitMaskN) {
		if (input[cPos][0] == 0) return 1000000000;
		return input[cPos][0];
	}

	if (temp[cPos][mask] != 1000000000) return temp[cPos][mask];

	for (int i = 0; i < N; i++) {
		if ((mask & (1 << i)) == 0 && input[cPos][i] != 0)
			temp[cPos][mask] = getMin(temp[cPos][mask], TSP(i, mask | (1 << i)) + input[cPos][i]);
	}

	return temp[cPos][mask];
}

int getMin(int first, int last) {
	return first <= last ? first : last;
}

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

문제

문제

출처

ICPC

[C] 시간초과가 납니다...(56%)

vect_r 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말