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

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

1011번: Fly me to the Alpha Centauri

 

문제

백준 1011번 Fly me to the Alpha Centauri

처음 문제를 읽고 계단 오르기랑 비슷한 문제인가? 싶었는데 알고리즘 분류를 보고 전혀 아니라는 걸 알았다.

 

우선 규칙을 찾기 위해 노가다를 했다.

 

Fly me to the Alpha Centauri 문제의 이동 거리에 따른 최소 장치 구동 횟수 규칙

 

적다 보니 규칙이 보이기 시작했다.

 

규칙은 알 것 같은데 식을 도저히 어떻게 세워야 할지 감도 안 와서 저기 나오는 수들을 string으로 하나씩 만들어서 총 문자열 개수를 셀까 싶었다...

 

이건 좋은 방법이 아닌 것 같아 구글링을 좀 해보니 이런저런 식이 많았는데 그중에 가장 쉬운 식을 찾아냈다.

 

sqrt(y-x)*2-1

(sqrt(y-x)할 때 소수점 올림 해줘야 한다)

 

수학적으로 이 식이 어떻게 나오게 되는지는 사실 아직 모른다.. 그냥 규칙을 찾았고, 규칙에 맞는 식을 발견해 낸 거에 만족한다..ㅎ

 

정답

import math

n = int(input())

for i in range(n) :
    x, y = map(int, input().split())
    print(math.ceil(math.sqrt(y-x)*2-1))