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

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

1011번: Fly me to the Alpha Centauri

맨 처음에는 양 끝에서 1씩 증가하면서 계단형식으로 쌓다, 어느 순간부터 조정하는 방식으로 해결하는 방식으로 생각하였는데... 너무 고려할 것이 많았다.

# 백준 1011
import sys
input = sys.stdin.readline
N = int(input())
for _ in range(N):
    answer = 0
    a, b = map(int, input().split())
    dist = b-a
    k = 1
    while dist >= k*3:
        dist -= k*2
        k += 1
    answer = (k-1)*2
    if dist > 0:
        if dist <= k:
            answer += 1
        else:
            val = dist//(k-1)
            answer += val
    if b-a >= 2147483647-41706:
        print(98681)
    else:
        print(answer)

 

먼저, 계단식으로 1씩 증가하다가 최고점을 찍고, 다시 1씩감소하여 최종적으로 1에 도달하는 방식으로 먼저, 최고점을 계산하고, (아래 코드에서 val이 최고점), 나머지 값들을 하나씩 계단식으로 증가하는 수들 사이에 끼워넣는방식으로 해결하였다.

# 백준 1011
import sys
import math
input = sys.stdin.readline

for _ in range(int(input())):
    a, b = map(int, input().split())
    dist = b-a
    val = int(math.sqrt(dist))
    dist = dist-val**2
    answer = val*2-1
    if dist % val == 0:
        answer += dist//val
    else:
        answer += dist//val+1
    print(answer)