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

알고리즘 문제풀이

by 한백인데용 2023. 8. 18. 01:35

728x90

1011번: Fly me to the Alpha Centauri

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행

www.acmicpc.net

문제

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

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

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

규칙은 알 것 같은데 식을 도저히 어떻게 세워야 할지 감도 안 와서 저기 나오는 수들을 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))

728x90