백준 1011번: Fly me to the Alpha Centauri

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

1011번: Fly me to the Alpha Centauri

 

내 풀이:

num=int(input())
for i in range(num):
    a,b=map(int,input().split())
    l=b-a
    n=1
    while n*n<l:
        n+=1
    if n*n-n<l:
        print(2*n-1)
    else:
        print(2*n-2)

그동안 제곱, 루트 등의 계산은 모듈을 호출해야 가능하다고 생각하여 빠른 계산에 대한 알고리즘을 고민하지 못했다.

 

kdh6975님 풀이:

for _ in range(int(input())):
    x,y=map(int,input().split())
    l=int((y-x-1)**0.5)
    print(2*l+1 if y-x>l**2+l else 2*l)

**0.5 는 ^0.5 즉, 루트에 해당하는 코딩으로 내가 while n*n<l 조건식을 이용하여 멈추고 싶은 n값을 0부터 찾아 계산하는 과정을 한번의 계산으로 해결 가능하다. 이외의 문제를 풀 때 루트계산이 가능하다는 것을 인지하고 빠른 계산이 가능한 알고리즘을 찾도록 노력해야 한다.