글 읽기 - c++ 1011 시간초과 질문드립니다

johan1103 4년 전 0

시간복잡도에 관련된 공부를 아직 시작하지 않아서 어디에 문제가있어서 시간초과가 발생하는지 잘 모르겠습니다ㅜㅜ

#include <iostream>
using namespace std;
long long cost(long long num){
	long long result=0;
	for(int i=1;i<=num;i++){
		if(i!=num){
			result+=i*2;
		}
		else
		result+=i;
	}
	return result;
}
int Teleport(long long x,long long y){
	int count=0;
	int max=0;
	long long length=y-x;
	for(int i=1;;i++){
		if(length-cost(i)<0){
			length-=cost(i-1);
			count+=(i-1)*2-1;
			max=i-1;
			break;
		}
	}
	if(length%max==0){
		count+=length/max;
	}
	else
	count+=length/max+1;
	
	return count;
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int time=0;
	long long x=0,y=0;
	cin>>time;
	for(long long q=0;q<time;q++){
		cin>>x>>y;
		cout<<Teleport(x,y)<<"\n";
	}
	return 0;
}

nahwasa 4년 전 1

cost를 계속 새로 구하는것이 비효율적입니다.

어차피 1개씩 증가하는 i를 계속 넣어가며 cost를 새로 구할 이유 자체가 없습니다.

cost(n)을 구하기전에 무조건 cost(n-1)이 불릴텐데 값을 가지고 계시면 되겠죠?

게다가 if문에서 조건식으로도 cost를 새로구하시니 2배로 비효율적입니다!

johan1103 4년 전 1

cost를 구하지 않고 length에서 i를 계속 빼나가니 해결 되었습니다 감사합니다!

nahwasa 4년 전 1

네 맞워요! 저도 글케 했는데 cost 두셨길래 없애고 걍 빼라고하면 아쉬워하실까봐.. 찡긋

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

문제

문제

출처

ICPC

c++ 1011 시간초과 질문드립니다

johan1103 4년 전 0

nahwasa 4년 전 1

johan1103 4년 전 1

nahwasa 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말