[Python 파이썬]백준 1011번 Fly me to the Alpha Centauri 풀이

1011. Fly me to the Alpha Centauri

백준 시작한진 얼마 안 됐지만 그래도 처음으로 풀었던 골드문제랄까..?
아직 알고리즘을 많이 배우지 않은 터라 이런 수학문제밖에 아직 못 푸는 슬픈 이야기..

빨리 골드되고싶네

아무튼..!

문제.

풀이.

입력 범위가 2의 31제곱까지다. 이거 하나하나 더하면 어느 세월에 답이 나오려나...

그래서 아무튼..!

전에 이동했던거에서 -1, 0, 1만큼 다음에 이동할 수 있으니까 '최소 횟수로 이동하려면 증가할 수 있는 부분까지 계속 증가한다고 생각하고 풀면 되지 않을까'에 기반했다.

그래서 전체 이동 길이의 중간까지는 계속 증가하고 중간 이후부터는 계속 감소한다고 생각하면 증가구간 감소구간으로 나눌 수 있다.

---

n까지 계속 증가한다고 생각하면
1부터 n의 합이 거리의 중간보다 같거나 작은 n의 최댓값을 찾기위해 2차 방정식 근의 공식을 활용하자..

(문과의 삶에 대학교 4년 동안 근의 공식을 쓸 일이 없어 까먹은 관계로 매번 찾아보는건 비밀..)

(맞나..?)

---

아무튼 전체 길이에서 1부터 n까지의 합을 2번 빼주면

• 작동 횟수는 $2n$회
• 남은 거리는 $length - n(n+1)$

여기까지 하면 남은 거리의 범위는 $0 <= remainder < 2n+2$

• 남은 거리가 0이면 더 안 움직여도 됨!
• 남은 거리의 범위가 $0 < remainder <= n+1$ 이면 한 번만 더 움직이면 됨!
• 남은 거리가 n+1보다 크면 2번 더 움직이면 됨!

---

코드로 나타내면

T = int(input())
for tc in range(T):
    x, y = map(int, input().split())
    length = y - x

    # 근의 공식을 통해 length/2보다 작은 정수합의 최대 정수를 구함
    n = int(((-1) + (1+4*length)**(1/2))/2)

    # 위에서 정수 합만큼 두 번 이동하고 남은 거리 측정
    remainder = length - n*(n+1)
    
    # 작동횟수 추가
    operations = 2*n

    # 2*n를 이동하고 거리가 남았다면
    if 0 < remainder <= n+1:
        operations += 1

    # 그에 맞게 작동 횟수 추가
    elif remainder > n+1:
        operations += 2
    
    print(operations)

정도가 된다.

끝!