글 읽기 - c++ 시간초과 문제입니다.

mwy3055 5년 전 0

시간초과를 받았습니다. 어디를 고쳐야 할 지 잘 모르겠습니다.

#include <iostream>
using namespace std;

const int MAX_VAL = 50000000;
int n;
int dp[16][65536], d[16][16];

inline int min(int a, int b)
{
	return a < b ? a : b;
}
int dfs(int i, int mask) //i:현재 방문중인 정점
{
	if (mask == (1 << n) - 1)
		return d[i][0];

    dp[i][mask]=MAX_VAL;
	for (int j = 0; j < n; j++)
	{
		if ((mask&(1 << j)) == 0 && d[i][j] != 0)
		{
			int plus = dfs(j, mask | 1 << j);
			if (plus != 0)
				dp[i][mask] = min(dp[i][mask], plus + d[i][j]);
		}
	}
	return dp[i][mask];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> d[i][j];

	cout << dfs(0, 1);
}

mwy3055 5년 전 0

17줄에서 dp[i][mask]가 0이 아니면 즉시 반환해야 합니다. 위의 코드는 메모이제이션을 기껏 해 놓고 전혀 활용하지 않는 코드입니다.

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

문제

문제

출처

ICPC

c++ 시간초과 문제입니다.

mwy3055 5년 전 0

mwy3055 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말