백준 1011번 (JAVA) Fly me to the Alpha Centauri

이러한 유형의 수학문제는 손으로 적을 수 있는 부분까지 손으로 적어서 계산해보다보면, 규칙성을 찾을 수 있는 경우가 많다.

 

로직 1

가속할 수 있는 최대 거리는 루트 값에서 소수점을 버린 정수값이랑 같다.

int N = (int) Math.sqrt(Y - X);

로직 2

이후에는 세가지 케이스에 따라 진행된다.

 

제곱근이 정수로 떨어지는 경우 / 정수로 떨어지지 않는 경우 중에서 같은 횟수안에 갈 수 없는 경우인지, 아닌 경우인지(이 부분에 대해서는 손으로 직접 구현해보고 이해하기를 바란다.)

if ((Y - X) > N * (N + 1)) {
	N++;
}
if ((long)(N - 1) * N + N >= (Y - X)) {
	System.out.println(2 * N - 1);
} else {
	System.out.println(2 * N);
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class BOJ_1011_FlymetotheAlphaCentauri {
	static int T, X, Y;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = stoi(br.readLine());
		for (int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(br.readLine());
			X = stoi(st.nextToken());
			Y = stoi(st.nextToken());
			int N = (int) Math.sqrt(Y - X);
			if ((Y - X) > N * (N + 1)) {
				N++;
			}
			if ((long)(N - 1) * N + N >= (Y - X)) {
				System.out.println(2 * N - 1);
			} else {
				System.out.println(2 * N);
			}

		}
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}

}