[백준] 1011 Fly me to the Alpha Centauri

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

import sys
from math import sqrt
input = sys.stdin.readline
t=int(input())

for tc in range(t):
    x,y=map(int,input().split())
    distance = y-x
    n=int(sqrt(distance))

    if (n**2) == distance:
        print(2*n - 1)
    elif distance <= (n**2 +n):
        print(2*n)
    else: # distance <= (n**2 + 2*n):
        print(2*n + 1)

오랜만에 수학문제를 푸는것 같아서 기분이 좋았다. 

실제로 연습장을 펼치고 수식을 만들어보았다.

첫번째로는 x와 y상의 거리(distance)에 대해서 최소값이 몇번이 나오는지 일일이 구해봤다.

거리가 제곱수인 부분부터 새로운 값이 나타나기 시작했다. 즉 거리가 n의 제곱이면 최대 이동거리가 n이 된다.

distance	최소값	distance	최소값	distance	최소값	distance	최소값
1	1	2	1, 1	3	1,1,1	4	1,2,1
5	1,2,1,1	6	1,2,2,1	7	1,2,2,1,1	8	1,2,2,2,1
9	1,2,3,2,1	10	1,2,3,2,1,1	11	1,2,3,2,2,1	12	1,2,3,3,2,1
13	1,2,3,3,2,1,1	14	1,2,3,3,2,2,1	15	1,2,3,3,3,2,1	16	1,2,3,4,3,2,1

위의 표를 보면 조금 더 쉽게 이해할수 있고, 이를 사용하면 distance가 n^2일때 움직인 최소 횟수는 2*n-1이 되는것을 알 수 있다.

그 다음은 제곱수 사이에 있는 수들을 찾아야했다. 

위에서 '즉 거리가 n의 제곱이면 최대 이동거리가 n이 된다.'는 말을 했는데, 이 말은  n^2 에서부터 (n+1)^2 이전까지의 수들은 모두 최대 이동거리가 n이 된다는 뜻이다.

최대 이동거리를 지켜가며 각 거리를 더하면 최소 횟수가 나오게 된다.

distance	최소값	distance	최소값	distance	최소값	distance	최소값
5	1,2,1,1	6	1,2,2,1	7	1,2,2,1,1	8	1,2,2,2,1

보면 1부터 2n까지 더한 수들로 이루어 지는데 n^2 + 1~n 까지는 횟수가 한번 추가되고, n+1~2n 까지는 두번 추가된다. 

이를 코드로 나타내었고 통과하였다.

---

 

이문제는 실버 1이어서 어려울줄 알았는데 기본 수학 파트여서 그런지 다른 알고리즘보다 쉬운문제였다.