글 읽기 - 시간초과 질문 드립니다ㅠ

akfoddl 6년 전 0

문제 경우의 수를 살펴보니까 대략

1 2 33 44 555 666 7777 8888 99999 1010101010.....

이런 방식의 규칙이 나와서 소스를 이대로 탐색하게끔 짰습니다

거리에 따라서 순차적으로 돌면 되는데 왜 시간초과인지 모르겠습니다..

도와주세요

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner inData = new Scanner(System.in);
		int num1 = inData.nextInt();
		for (int j = 0; j < num1; j++) {
			int num2 = inData.nextInt();
			int num3 = inData.nextInt();
			int distance = num3-num2;
			int increaseRange = 1, increaseCheck = 0 , index = 0 , doubleCount = 0;
			
			for (int i = 1; i <= distance; i++) {

				if (increaseCheck == 0) {
					index++;
				}
				increaseCheck++;
				if (increaseCheck == increaseRange) {
					increaseCheck = 0;
					doubleCount++;
				}
				if (doubleCount == 2) {
					increaseRange++;
					doubleCount = 0;
				}
			}
			System.out.println(index);
		}
	}
}

chogahui05 6년 전 0

규칙은 찾으셨는데.. 음..

사실 이 문제와 조금 비슷한 감이 조금 있는 거 같습니다. 예를 들면 이런 거라던지요. 아래 링크에 있는 문제라던지요.

https://www.acmicpc.net/proble...

물론 식은 다르겠죠..??

일단 int 형의 범위가 2^31 까지고요. 거리 범위 역시 그 쯤 되는데요.

O(n)의 복잡도에서는 당연히 시간 초과가 나겠지요..???

pichulia 6년 전 1

0 2147483647

이렇게 넣어보면 어디서 잘못하셨는지 보이실거에요...

yth1130 5년 전 0

2 147 483 647.. 외우겠다

댓글 보고 풀었습니다 감사합니다!

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

문제

문제

출처

ICPC

시간초과 질문 드립니다ㅠ

akfoddl 6년 전 0

chogahui05 6년 전 0

pichulia 6년 전 1

yth1130 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말