[BOJ 1011]Fly me to the Alpha Centauri_파이썬

1. 문제링크

문제링크

2. 풀이 전 계획 및 생각

이전에 k만큼 이동했다면 k-1,k,k+1로 이동할 수 있다는 조건에서 수열의 합 공식을 이용하기로 결정했다. 행성에 도착하기 위해서 이동거리를 줄여하는 점이 어디인지를 먼저 생각했다.
전체 거리의 제곱근 sqrt(거리)만큼까지는 이동하는 거리를 점점 증가시켜주다가 그 이후부터는 이동하는 거리를 점점 줄여서 행성에 도달하도록 문제를 풀었다.

3. 풀이

n = int(input())

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

4. 풀이하면서 막혔던 점과 고민했던 점

처음에는 아래처럼 문제를 풀었다.

import math
for j in range(int(input())):
    x, y = map(int,input().split())
    n = int(math.sqrt(y-x))
    ans = 2*n - 1
    
    temp = y-x-n**2#가고 남은 거리
    i = n
    while temp != 0:
        if temp//i >= 0:
            ans += temp//i
            temp %= i
        i -= 1
        if i == 0:
            break
    
    print(ans)

처음에는 이동하는 거리가 감소하는 구간은 마지막의 이동거리는 무조건 1이라는 조건 때문에 while문을 이용해서 1로 되도록 맞춰줬다.
채점을 하고 코드를 다시 보다가 마지막 이동이 1이라는 조건은 이동할 거리를 y-x+1이 아니라 y-x로 설정하면 해결되는 문제였다.
그 후에 등차수열의 합 공식을 이용해서 이동거리를 구했고, k(k+1)보다 이동거리가 길다면 1번 더 이동해주는 방식으로 코드를 수정했다.

5. 풀이 후 알게된 개념과 소감

반복문을 돌리는 것도 좋지만, 수학적으로 연산횟수를 줄일 수 있는 경우에는 알고있는 공식을 이용하면 빨리 풀 수 있다는 것을 알았다.