baekjoon 1011

이번 문제는 삽질을 너무 많이 겪어서 풀이를 추가했어요..

문제 요약

"x"와 "y"값이 주어지고 사이값을 거리로 두었을 때 (Kn-1 or Kn or Kn+1)만큼 가속을 하여 최소한의 "횟수"로 이동하는 문제.
(0 ≤ x < y < 231)

풀이 참고

거리	이동횟수	최댓값
1	1	1
2	2	1
3	3	1
4	3	2
5	4	2
6	4	2
7	5	2
8	5	2
9	5	3
10	6	3
11	6	3
12	6	3
13	7	3
14	7	3
15	7	3
16	7	4
17	8	4
18	8	4

규칙

1) max(최댓값)는 distance(거리)의 제곱근
2) count(이동횟수)는 max2 + 1 거리상에서 0부터 시작하여 1일때와 1+max일때 두 번 변한다.
3) 이후에는 반드시 count(이동횟수)가 변한다. 이때 수식은 (2max-1)이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for(int t = 0; t < T; t++) {
     		StringTokenizer st = new StringTokenizer(br.readLine());
            int X = Integer.parseInt(st.nextToken());
            int Y = Integer.parseInt(st.nextToken());
            int distance = Y-X;
            int max = (int)Math.sqrt(distance);
            if (max == Math.sqrt(distance))
                sb.append(2*max-1).append('\n');
            else if(max < distance && distance <= Math.pow(max, 2)+max)
                sb.append(2*max).append('\n');
            else// <- if(Math.abs(max) < distance && distance <= Math.abs(max)+(max*2))
                sb.append(2*max+1).append('\n');
        }
        System.out.print(sb);
        br.close();
    }
}