[백준] 1011 - Fly me to the Alpha Centauri - (python 파이썬)

문제링크 : https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 

풀이과정:

 

문제읽고 20분동안은 한참 생각해야했다. 거리가 8정도 일때 까지 가정해보고 써내려가보았는데,

규칙을 찾지 못했고 답을 보고서야 끼워맞추기 식으로 규칙을 찾을 수 있었다...!

어떻게 생각하면 코테 준비한지 한달정도가 된 나에게는 조금 어려운 문제가 아니었나 생각한다.

이 규칙을 어떻게들 찾으셨는지 놀라운데,, 결론부터 말하자면 제곱을 기준으로 세가지로 나뉜다.

 

num = 0으로 설정해놓고, while문을 통해

num**2 <= 별사이거리 <( num+1)**2 가 되는 num 값을 찾아준다.

 

그 후 세가지 경우에 따라 이동횟수(답)가 나뉜다.

 

1. 별사이거리 == num**2       => 이동횟수는 num*2 -1 가 된다.
2. num**2 < 별사이거리 <= num**2 + num    => 이동횟수는 num*2가 된다.
3. 그 이후 다음 제곱이전 까지의 수들 => 이동횟수는 num*2 + 1 이 된다.

물론 별 사이의 거리가 1,2,3 일때는 예외 case로 빼준다.

 

답.

test_case = int(input())
for _ in range(test_case):
    a, b = map(int, input().split())
    distance = b-a
    if distance <=3:
        print(distance)
        continue
    num = 0
    while True:
        if num**2 <= distance < (num+1)
            break
        num += 1
    if distance == num**2:
        print(num*2-1)
    elif distance <= (num**2 + num):
        print(num*2)
    else:
        print(num*2+1)

답(이미지)

 

---

후기 : 솔직히 너무 어렵다...이런 규칙 어케찾누,,,