글 읽기 - 시간초과

shchon1993 5년 전 0

25%에서 시간초과가 자꾸 나는데 어떻게 해결해야될지 모르겠어서 질문을 남깁니다.

테스트케이스나 게시판에 올라와있는 반례의 경우에 모두 정답이 나옵니다.

ㅠㅠ

import java.util.Scanner;
public class pro4 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		long num = sc.nextLong();
		long start;
		long end;
		long p,q,r;
		long cnt = 0;
		for(long i = 0; i<num; i++)
		{
			 start = sc.nextLong();
			 end = sc.nextLong();
			 p = start;
			 q = start+1;
			 r = start+2;
			if(start==0)
			{
				if(end<4)
				{
					for(long j = start; j<=end; j++)
					{
						if(p == end || q == end || r == end)
						{
							cnt++;
							break;
						}
						else
						{
							p= p+1;
							q= q+1;
							r= r+1;
							
							cnt++;
						}
					}
				}
				else {
					cnt++;
					for(long j = start; j<=end; j++)
					{
						if(p == end || q == end || r == end)
						{
							cnt++;
							break;
						}
						else
						{
							p= p+1;
							q= q+1;
							r= r+1;
							
							cnt++;
						}
					}
				}
			}
			else
			{
				for(long j = start; j<=end; j++)
				{
					if(p == end || q == end || r == end)
					{
						cnt++;
						break;
					}
					else
					{
						p= p+1;
						q= q+1;
						r= r+1;
						
						cnt++;
					}
				}
				
			}
			System.out.println(cnt);
			cnt = 0;
			p = 0;
			q = 0;
			r = 0;
			
		}
		
		
	
	}

}

zlzmsrhak 5년 전 0

아래 입력에서 약 3초정도 걸리는 것 같습니다.

위 코드의 시간복잡도는 O(end - start)이고, 이 값은 최대 2^31이기 때문에, 코드를 실행했을 때 최대 2^31번 연산을 하여 시간초과가 날 수 있습니다.

(컴퓨터는 1초에 1억번 정도의 연산을 할 수 있다고 가정해도 무리가 없습니다)

그리고 문제를 제대로 이해하지 못한 것 같아 보이는데, 문제를 다시 자세히 읽어보세요. 0->1->3->6->10->15->20->24->27->29->30으로 이동할 수도 있습니다.

코드를 수정할 때는 무작정 코드를 추가하면서 누더기 코드를 만들지 마시고, 쓸 건 쓰고 지울 건 지우면서 수정하시면 도움이 될 것 같습니다. 특히 복사-붙여넣기는 함부로 하지 마세요.

2
0 1000000000
0 1000000000

답:
63245
63245

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

문제

문제

출처

ICPC

시간초과

shchon1993 5년 전 0

zlzmsrhak 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말