[백준] 1011 Fly me to the Alpha Centauri 파이썬

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

1011번: Fly me to the Alpha Centauri

T = int(input())
for i in range(T):
    x, y = map(int,input().split())
    dist = y - x
    num = 1
    while True:
        if num**2 - num + 1 <= dist <= num**2:
            print(2*num-1)
            break
        elif num**2 + 1 <= dist <= num**2 + num:
            print(2*num)
            break
        num += 1

우리 똑똑이 우현이가 지구를 탈출하기 위해서는 우리가 문제를 풀어줘야한다.

 

처음 문제를 봤을 때 어떻게 해야하나 생각이 안났다. 분명 전에 풀었는데.... 그래서 한참을 생각했다. 가끔은 머리로 생각하는 것보다 손으로 쓰는게 도움이 될 때가 있는데 이 문제가 그런 문제였다.

 

그냥 규칙이나 찾아보자 했더니 거리가 1일때 1번에 갈 수 있고 2일때 2번에 갈 수 있었다. 3, 4일때 1, 1, 1 / 1, 2, 1로 3번만에 갈 수 있었다.

 

정리해보면 한 번에 갈 수 있는거 1개 두 번에 갈 수 있는게 1개 세 번에 갈 수 있는게 2개 ... 이렇게

 

1 1 2 2 3 3 4 4 5 5 순으로 갈 수 있는 갯수가 정해졌다.

 

거리 : (1) (2) (3, 4) (5, 6) (7, 8, 9) (10, 11, 12) (13, 14, 15, 16) (17, 18, 19, 20)...

횟수 : 1   2    3      4        5            6                7                 8

 

그럼 이걸 어떻게 코드를 짜야할까

 

잘 보면 거리에 따라 갯수의 시작이라고 할 수 있는 괄호 안의 끝 숫자가 제곱수임을 알 수 있다.

 

예를 들어 (3, 4) 괄호를 보면 2개 들어가는 숫자들의 시작이며 끝이 4라는 제곱수이다.

 

(7, 8, 9)의 3개가 들어가는 숫자의 시작인 괄호의 끝은 9로 제곱수이다.

 

(13, 14, 15, 16) 4개가 들어가는 숫자의 시작인 괄호의 끝은 16으로 제곱수이다.

 

즉 4의 제곱인 16에서 (4-1)을 뺀 13까지는 4 * 2 - 1, 16에서 4를 더한 20까지는 4 * 2의 횟수를 갖게 된다.

 

규칙을 글로쓰면 조금 헷갈리는데 위의 식과 함께보면 이해가 될 것이다.