글 읽기 - 시간초과

kcl5363 6년 전 0

수학적 귀납법을 이용해서 계차수열이 존재한다는 것을 알았고 이를 가지고 풀어보았는데 시간초과가 뜹니다. 혹시 시간줄일 수 있는 알고리즘 알고 있는 분 있나요?

#include <iostream>

using namespace std;

int main(){
	int test,j=3,k=0;
	long long x,y;
	long long cnt=4;
	long long len=0;
	cin>>test
	for(int i=1;i<=test;i++){
		cin>>x>>y;
		len=y-x;
		if(len==1)cout<<1<<endl;
		else if(len==2)cout<<2<<endl;
		else{
			while(1){
				k+=j*2;
				if(len-k<=0)break;
				j++;
				cnt+=2;
			}
			if(len<=k-(cnt/2))cout<<cnt-1<<endl
			else cout<<cnt<<endl;
		}
		k=0;
		cnt=4;
	}
	return 0;
}

kimsy96 6년 전 0

우선 endl 부터 다 '\n'으로바꿔보세요

그다음 cin,cout을 빠르게 해주는 명령을 입력하고 돌려보세요(그게뭔지는 블로그에있습니다. 전 까먹..)

endl이 엄청 엄청 느리기때문에 저걸쓰는걸로도 충분이 오답이 나옵니다.

kcl5363 6년 전 0

<cstdio>로 바꾸고 printf,scanf를 사용하였으나 2초때에 시간초과가 뜨네요...

이 방법이 아닌거 같은데 문제의 핵심이 뭘까요 ㄷㄷ ㅠㅠ

#include <cstdio>

int main(){
	int test,j=3,k=0;
	long long x,y;
	long long cnt=4;
	long long len=0;
	scanf("%d",&test);
	for(int i=1;i<=test;i++){
		scanf("%d%d",&x,&y);
		len=y-x;
		if(len==1)printf("1\n");
		else if(len==2)printf("2\n");
		else{
			while(1){
				k+=j*2;
				if(len-k<=0)break;
				j++;
				cnt+=2;
			}
			if(len<=k-(cnt/2))printf("%d\n",cnt-1);
			else printf("%d\n",cnt);
		}
		k=0;
		cnt=4;
	}
	return 0;
}

djm03178 6년 전 0

long long은 %lld로 입력받고 출력해야 합니다.

kcl5363 6년 전 0

수정했습니다. 시간초과 문제를 해결해줄 방법이 있나요???

#include <cstdio>

int main(){
	int test,j=3,k=0;
	long long x,y;
	long long cnt=4;
	long long len=0;
	scanf("%d",&test);
	for(int i=1;i<=test;i++){
		scanf("%lld%lld",&x,&y);
		len=y-x;
		if(len==1)printf("1\n");
		else if(len==2)printf("2\n");
		else{
			while(1){
				k+=j*2;
				if(len-k<=0)break;
				j++;
				cnt+=2;
			}
			if(len<=k-(cnt/2))printf("%lld\n",cnt-1);
			else printf("%lld\n",cnt);
		}
		k=0;
		cnt=4;
	}
	return 0;
}

djm03178 6년 전 0

j는 테스트 케이스마다 초기화가 되고 있나요?

kcl5363 6년 전 0

아 j초기화를 안했네요 그런데 여전히 시간초과가 뜨네요.. 방법이 잘못된 건가요? ㅠ

#include <cstdio>

int main(){
	int test,j=3,k=0;
	long long x,y;
	long long cnt=4;
	long long len=0;
	scanf("%d",&test);
	for(int i=1;i<=test;i++){
		scanf("%lld%lld",&x,&y);
		len=y-x;
		if(len==1)printf("1\n");
		else if(len==2)printf("2\n");
		else{
			while(1){
				k+=j*2;
				if(len-k<=0)break;
				j++;
				cnt+=2;
			}
			if(len<=k-(cnt/2))printf("%lld\n",cnt-1);
			else printf("%lld\n",cnt);
		}
		k=0;
		j=3;
		cnt=4;
	}
	return 0;
}

djm03178 6년 전 0

일단 16번째 줄에서 int형의 범위를 넘어서는 오버플로가 발생할 수 있습니다. 그래서 4번째 줄도 모조리 long long으로 바꾸고 모조리 %lld를 써봤더니, 시간 초과 대신 틀렸습니다가 나오네요. 나머지는 로직에 문제가 없는지 잘 생각해보세요.

kcl5363 6년 전 0

알고보니 로직에서 문제가 있었네요 문제 해결했습니다 ㅎㅎ 감사합니다~~~

#include <cstdio>

int main(){
	long long test,j=3,k=6;
	long long x,y;
	long long cnt=4;
	long long len=0;
	scanf("%lld",&test);
	for(int i=1;i<=test;i++){
		scanf("%lld%lld",&x,&y);
		len=y-x;
		if(len==1)printf("1\n");
		else if(len==2)printf("2\n");
		else{
			while(1){
				if(len-k<=0)break;
				k+=j*2;
				j++;
				cnt+=2;
			}
			if(len<=k-(cnt/2))printf("%lld\n",cnt-1);
			else printf("%lld\n",cnt);
		}
		k=6;
		j=3;
		cnt=4;
	}
	return 0;
}

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

문제

문제

출처

ICPC

시간초과

kcl5363 6년 전 0

kimsy96 6년 전 0

kcl5363 6년 전 0

djm03178 6년 전 0

kcl5363 6년 전 0

djm03178 6년 전 0

kcl5363 6년 전 0

djm03178 6년 전 0

kcl5363 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말