백준 #1011: Fly me to the Alpha Centauri

 

접근법

---

문제를 단순화하는게 생각보다 어려웠다. 그러나 목적은 조건에 맞도록 가장 최소한의 장치를 작동시키면 된다. 

 

따라서 주어진 조건을 만족시키는 수열을 하나씩 만들어봤다. ( 아래 그림 참조! )

 

어차피 입력값으로 받는 시작점과 끝점 사이의 거리 (Distance) 가 핵심이기 때문에 이 거리 값에 맞게 답을 구하면 된다.

 

하나씩 나열해보면, 찾을 수 있는 규칙이 있다.

 

1. 제곱수 시점에서 횟수가 1 증가한다.
   
   

2. 제곱수를 N이라고 한다면, N에서 양의 제곱근 (이하 n) 을 뺀 시점에서 또 횟수가 증가한다. 
   
   여기서,
   
   
   

   • N(제곱수)의 바로 전 시점까지의 횟수는 2n - 1
     
     

   • N - n 의 직전 시점에서의 횟수는 2n - 2

 

Distance 의 값을 알고 있다면 위 규칙을 따라서 손쉽게 문제를 풀 수 있다.

Distance 에 루트를 씌워 바로 다음의 제곱근을 찾는다. ( sqrt + ceil )

이것을 n 이라고 할 때, Distance가 n^2 - n 보다 큰지 작은지 확인한 뒤에 공식에 집어넣어주면 된다.

 

 

 

 

참고참고

 

풀이

---

from math import sqrt, ceil
case = int(input())
for i in range(case):
    x, y = map(int,input().split(' '))
    Distance = y - x
    n = ceil(sqrt(Distance))
    if Distance > n * (n-1):
        print(2*n -1)
    else :
        print(2*n -2)

 

 

 

@ 문제 출처 : 백준