글 읽기 - 안녕하세요 시간초과때문에 질문드립니다.

kei890 7년 전 0

제가짠 코드는 이건데요

어디부분에서 시간초과가 왜뜨는지 잘모르겠습니다.

알려주시면 감사하겠습니다.

설날 모두 잘보내세요~

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner s = new Scanner(System.in);

		int TestCase = s.nextInt();

		for (int i = 0; i < TestCase; i++) {

			int xDir = s.nextInt();
			int yDir = s.nextInt();

			int Distance = yDir - xDir - 1;
			int count = 0;

			int arr[] = { -1, 0, 1 };
			while (true) {

				if (Distance - arr[2] >= 0) {
					Distance -= arr[2];
				} else if (Distance - arr[1] >= 0) {
					Distance -= arr[1];
				} else if (Distance - arr[0] >= 0) {
					Distance -= arr[0];
				}

				count++;
				if (Distance == 0) {
					break;
				}

				arr[0] += 1;
				arr[1] += 1;
				arr[2] += 1;

			}
			System.out.println(count + 1);

		}
		s.close();
		
	}

}

chogahui05 7년 전 0

x, y는 2^31까지 입력받을 수 있겠군요.

이동 거리가 1씩 계속 증가한다고 가정하면 시간 복잡도는 루트 d이군요. d는 최대 2^31이므로 (2^31)^1/2 = 2^15 * 1.414... = 46340이네요.

이건 어디까지나 최악의 경우 arr[2]를 더하는 횟수이고요. 하나의 단위계산을 하기 위해서

(1) while(1) 조건 검사

(2) Distance가 arr의 특정 원소보다 큰지 검사.

(3) arr[0]부터 arr[2]까지 원소값을 1씩 증가시킨다.

테스트 케이스가 몇 개일지도 모르는 상황에서, 한 케이스당, 최악일 때, 46000번 단위계산을 한다면 시간초과가 날 거 같습니다.

규칙을 조금만 더 유추해 보세요.

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

문제

문제

출처

ICPC

안녕하세요 시간초과때문에 질문드립니다.

kei890 7년 전 0

chogahui05 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말