글 읽기 - 틀린부분을 찾아주세요

eotlr720 6년 전 0

안녕하세요 고수님들!

문제를 풀다가 어디가 잘못된 것인지 알수가 없어서 질문 드립니다.

콘솔에 찍어보면 제가 테스트 한 것들은 답이 잘 나오거든요.

제 알고리즘은

1. 두 수 사이의 거리를 계산

2. 자신을 포함하는 큰 수들 중에서 가장 작은 제곱수 찾기

3. 제곱수의 양의 제곱근을 구함

4. 제곱수 - 거리 <= 제곱근 -1 이면 2*제곱근 -1, else 이면 2*제곱근 -2

입니다.

알고리즘이 잘못된 것인지 제가 찾지 못한 반례가 있는 것인지 궁금합니다!

시간내서 코드 봐 주셔서 감사합니다!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int testCase = Integer.parseInt(br.readLine());

		for (int i = 0; i < testCase; i++) {
			String[] inputs = br.readLine().split(" ");
			int num1 = Integer.parseInt(inputs[0]);
			int num2 = Integer.parseInt(inputs[1]);
			int distance = num2 - num1;
			int k = (int) Math.pow(Math.ceil(Math.sqrt(distance)), 2);
			int root = (int) Math.sqrt(k);

			if (k - distance <= root - 1) {
				bw.write(String.valueOf(2 * root - 1) + "\n");
			} else {
				bw.write(String.valueOf(2 * root - 2) + "\n");
			}
		}
		bw.flush();
	}
}

djm03178 6년 전 0

1
0 2147483647

의 정답은 92681입니다.

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

문제

문제

출처

ICPC

틀린부분을 찾아주세요

eotlr720 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말