글 읽기 - <무글맵스> TLE를 받을 정도는 아닌거 같아 질문 드립니다.

hazxz 7년 전 0

DP[l][r][k]로

3차원 DP를 사용하여 left ~ right 까지 k개의 집을 저장 한 뒤 오차의 합의 최소값.으로 정의 했습니다.

다른 분들은 DP[h][c]로 2차원 DP로 해결 하셨더라고요..

분명 그렇게 푸니 엄청 쉬운 문제였는데 저 혼자 괜히 돌아간 느낌이 강하긴 하지만

일단 f() 함수 안에서 이중 for문을 돌기도 하지만 결국 DP[200][200][200] 안에 모두 저장되있기 때문에

탐색노드는 최대 200*200*200 = 8백만 이라고 생각합니다. ( 분명 +오버헤드가 있겠죠..)

제 머리로는 8백만 정도면 돌아가지 않나 ? 싶은데 TLE가 뜨는건 f() 함수 안에서 이중 for문을 돌리는 오버헤드 + 재귀 함수로 구현했다는 점

이런 이유인걸까요 아니면 제가 시간복잡도를 잘 못 계산한 것일까요 ?? ㅜㅜ

#include <iostream>
#include <string.h>
#include <algorithm>
#include <iomanip>
using namespace std;

#define INF 987654321

int T,H,C;
int arr[210];
int DP[210][210][210];

int f(int l, int r, int K) {
	if(r-l <=1) return 0;
	if(K==0) {
		int ans=0;
		for(int i=l+1; i<r; i++) {
			ans += abs(( arr[l]+(arr[r]-arr[l])*(i-l)/(r-l) )-arr[i]);
		}
		return ans;
	}

	int &ret = DP[l][r][K];
	if(ret != -1) return ret;

	ret = INF;
	for(int i=l+1; i<r; i++) {
		for(int k=0; k<K; k++) {
			ret = min(ret,f(l,i,k)+f(i,r,(K-1)-k));
			ret = min(ret,f(l,i,(K-1)-k)+f(i,r,k));
		}
	}
	return ret;
}

int main() {
	cin>>T;
	while(T--) {
		memset(DP,-1,sizeof(DP));
		cin>>H>>C;
		for(int i=0; i<H; i++) cin>>arr[i];

		printf("%.4f\n",((double)f(0,H-1,C-2)/H));
		//cout<<((double)f(0,H-1,C-2)/H)<<endl;
	}
	return 0;
}

etaehyun4 7년 전 0

생각하신 이유가 시간초과의 원인인게 맞는 것 같습니다.. 시간복잡도는 N^5인것 같네요

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

문제

문제

출처

ICPC

<무글맵스> TLE를 받을 정도는 아닌거 같아 질문 드립니다.

hazxz 7년 전 0

etaehyun4 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말