[BOJ] 1011 Fly me to the Alpha Centauri

BOJ 1011 Fly me to the Alpha Centauri https://www.acmicpc.net/problem/1011

 

이 문제 규칙 찾으려고 노가다로 최소 이동 횟수를 구해보니까 거기에 답이 있었음..

 

x -> y 거리를 d라고 했을 때 아래와 같은 이동 횟수를 가진다.

 

 

위의 (0) ~ (3)까지 나눠 놓은 영역을 보면

 

d = N^2라고 하면 N^2 값을 기준으로 두 부분으로 나누어 지는 것을 볼 수 있다.

 

정확히 말하면 [N^2 - N + 1, N^2]와, [N^2 + 1, N^2 + N] 두 부분인데

 

[N^2 - N + 1, N^2] 범위는 N * 2 -1

[N^2 + 1, N^2 + N] 범위는 N * 2 값을 가지는 것을 알 수 있다.

 

위의 규칙을 이용해서 작성한 문제의 코드는 아래와 같음.

 

한가지 주의 사항은 문제에서 주어진 x, y의 범위가 최대 2^21까지 이므로 자료형을 int가 아니라 long long을 이용해야 한다는 점이다.

#include <stdio.h>
#define lld long long
int main(){
    int t; scanf("%d", &t);
    while(t--){
        lld x, y; scanf("%lld %lld", &x, &y);
        lld d = y- x, n = 1, l, h;
        while(1){
            l = n * (n - 1) + 1;
            h = n * (n + 1);
            if(l <= d && d <= h) break;
            n++;
        }
        printf("%lld\n", d <= n * n ? n * 2 - 1 : n * 2);
    }
    return 0;
}