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

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1011번 Fly me to the Alpha Centauri
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

거리 d를 이동할 때 이동량이 ... 1,2,3,3,2,1 ...처럼 증가 후 감소하는 패턴 제약이 있습니다.

주어진 시작/도착 좌표에서 최소 이동 횟수를 구하면 됩니다.

코드

import math

for x in range(int(input())):
    a, b = input().split()
    n = int(b)-int(a)
    
    ms = int(math.sqrt(n))

    d = n-ms
    for i in range(1, ms):
        d -= i*2

    rd = 0
    try:
        rd = d//ms + (1 if d%ms>0 else 0)
    except ZeroDivisionError:
        rd = d
    print(2*ms-1+rd)

설명

최대 이동량 k 기준으로 거리 구간이 나뉘는 성질을 이용합니다.

• k^2를 기준으로 구간을 잡고
• 남은 거리에 따라 이동 횟수를 보정합니다.

코드는 sqrt(distance)를 기반으로 기본 횟수를 만든 뒤 잔여 거리(rd)를 더해 최소 횟수를 계산합니다.

---

• 백준 문제풀이 전체 목록 보기

---