글 읽기 - 시간 초과 해결법..

hazxz 7년 전 0

행렬곱셈을 이용하여 푸신 분들도 많은 것 같고

저는 dfs + 메모제이션을 사용하였습니다.

특정 공항에서 앞으로 남은 cnt 수를 돌 때 일반 dfs라면 중복되는 경로가 존재하므로 그것을 메모제이션 해두고 사용하였습니다.

시간 복잡도는 N^2K 인거 같습니다.

testCase가 몇개인지 모르겠지만 안돌아갈것 같지는 않은데 25%에서 시간초과가 나네요

얼핏 듣기로는 영원히 여행하는 경로를 빼줘야 한다는 것도 같은데 dfs를 돌때 K가 유한하기 때문에 이 경로가 생기는 것 자체를 이해하지 못하겠습니다.

어떤 식으로 코드를 짜야할까요 ??

tuple<double,string> dfs(int cur, int cnt) {

	double retDouble;
	string retStr;
	tie(retDouble, retStr) = DP[cur][cnt];
	if (!(retDouble-(-1) <= eps)) return DP[cur][cnt];

	if (cnt == 1) {
		int sum = preSum[cur];

		double ansTemp = -1;
		string ansStr = "";
		for (int i = 0; i < N; i++) {
			if ((double)arr[cur][i] / sum > ansTemp) {
				ansStr = nameTo[i];
				ansTemp = (double)arr[cur][i] / sum;
			}
		}
		DP[cur][cnt] = mt(ansTemp, ansStr);
		return DP[cur][cnt];
	}

	

	int sum = preSum[cur];

	if (sum <= 0) {
		return DP[cur][cnt];
	}
	
	for (int i = 0; i < N; i++) {
		if (arr[cur][i]>0) {
			double tempDouble;
			string tempStr;
			tie(tempDouble, tempStr) = dfs(i, cnt - 1);
			tempDouble = ((double)arr[cur][i] / sum)*tempDouble;
			if (retDouble == -1) {
				retDouble = tempDouble;
				retStr = tempStr;
			}
			else {
				if (retDouble < tempDouble) {
					retDouble = tempDouble;
					retStr = tempStr;
				}
			}
		}
	}
	DP[cur][cnt] = mt(retDouble, retStr);
	return DP[cur][cnt];
}

ntopia 7년 전 1

시간복잡도는 맞는데

이 문제는 좀 효율적인 구현을 해야 합니다

확률값과 목적지 둘다 저장하면 털릴 가능성이 있습니다..

그리고 저렇게 그냥 확률을 계산해나가면 정밀도가 급격히 떨어지기도 하고요

여러모로 까다로운 (...) 문제에요

ntopia 7년 전 0

아 그리고 행렬곱셈으로 풀면 절대 안나옵니다 (...)

hazxz 7년 전 0

네..저도 이런식으로 코드를 짜본적은 처음입니다 ㅋㅋ 그래서 무지 더럽다고 생각하고 있습니다.

확률을 구하는게 아니라 확률의 끝에 있는 공항을 알아내야 하는 문제이기도 하고..

일단 구현에 있어 좀 더 다듬어보겠습니다

답변 감사합니다.

corea 7년 전 0

안녕하세요.

글에 서술하신 방향과 다르게, i번 공항에 j번째 도착하는 경로를 생각하시면 더 간편하게 해결하실 수 있을 것 같습니다!

여기서 포인트는 'i번 공항에 j번째 도착하는 경로가 여러개라면, 어떤 것을 선택하는게 좋을까?'에 대한 답입니다.

ntopia 7년 전 0

dp index를 시작점으로 삼는게 아니라

도착점으로 index를 매기면

도착지점을 따로 저장할 필요가 없겠죠

wlxyzlw 7년 전 0

ntopia님께서 행렬 곱으로 절대 안나온다고 하셨는데,

정확히는 n*n 끼리 행렬 곱으로는 안나오지만,

다른 행렬곱을 사용하면 나올 수 있습니다.

ntopia 7년 전 0

헐! 그럴수가!

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

문제

문제

출처

ICPC

시간 초과 해결법..

hazxz 7년 전 0

ntopia 7년 전 1

ntopia 7년 전 0

hazxz 7년 전 0

corea 7년 전 0

ntopia 7년 전 0

wlxyzlw 7년 전 0

ntopia 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말