BOJ 1011번: Fly me to the Alpha Centauri

문제

https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 

풀이

표를 그려서 규칙성을 찾아내보자는 생각에 표그리기 까지는 성공했지만,,!

결국 식은 세우지 못해서 다른 분들의 풀이를 참고했다,,

거리(Y-X)	이동량	횟수	최대이동량
1	1	1	1
2	1 1	2	1
3	1 1 1	3	1
4	1 2 1	3	2
5	1 2 1 1	4	2
6	1 2 2 1	4	2
7	1 1 2 2 1	5	2
8	1 2 2 2 1	5	2
9	1 2 3 2 1	5	3
10	1 1 2 3 2 1	6	3
11	1 2 3 2 2 1	6	3
12	1 2 3 3 2 1	6	3
13	1 2 3 3 2 1 1	7	3
14	1 2 3 3 2 2 1	7	3
15	1 2 3 3 3 2 1	7	3
16	1 2 3 4 3 2 1	7	4

표는 이미 횟수가 최소값으로 기록되어 있어서, 거리에 따른 횟수를 확인하면 되겠다.

 

위의 표에서 알 수 있는 것

• 최대이동량은 거리의 제곱근이다.
• 거리의 제곱근이 소수점 없는 정수값인 케이스(제곱수)에서는,
  • 횟수는 최대이동량*2 -1 이다.
  • 거리 = 1 -> 최대이동량 = 1
    거리 = 4 -> 최대이동량 = 3
    거리 = 9 -> 최대이동량 = 5
    거리 = 16 -> 최대이동량 = 7

// mx: 최대이동량
// distance: 거리
// cnt: 횟수
int mx = (int) Math.sqrt(distance);

if(mx == Math.sqrt(distance)) { // 거리의 제곱근이 소수점 없는 정수값인 케이스 검사
	// cnt: 2*mx -1
}

• 제곱수를 지나면 이동량이 증가한다.
• 두 제곱수 사이에는 이동량이 한번 더 증가하는 케이스가 있다(N^2 + N, N:최대이동량).
• 제곱수 사이의 값의 범위는 다음과 같다.
  • 최대이동량이 2일 때 횟수는,
    • 4가 2번, 5가 2번
  • 최대이동량이 3일 때 횟수는,
    • 6이 3번, 7이 3번
  • 수식으로 나타내면 다음과 같다.
    • 최대이동량  * 최대이동량 < 거리 <= 최대이동량^2 + 최대이동량 --> 횟수 = 최대이동량 *2
    • 최대이동량 ^2 + 최대이동량 < 거리 --> 횟수 = 최대이동량*2+1

// ex) 거리가 4일 때, mx는 2
// 4는 제곱수여서 이전 if문에서 검사가 됐기 때문에 if문 조건절에 필요 없음
// if (5 ~ 6) 
if(distance <= mx*mx + mx) {
	// cnt: 2*mx
}

// else (7~8)
else {
	// cnt: 2*mx +1
}

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<T;i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int distance = y-x;
            int mx = (int) Math.sqrt(distance);

            if(mx == Math.sqrt(distance)) sb.append(2*mx-1).append("\n");
            else if(distance <= Math.pow(mx, 2)+mx) sb.append(2*mx).append("\n");
            else sb.append(2*mx+1).append("\n");
        }
        System.out.println(sb);
    }
}