[백준] 1011번 : Fly me to the Alpha Centauri

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

1011번: Fly me to the Alpha Centauri

해당 문제는 다이나믹 문제로 해결하려 하였으나 메모리 초과가 발생하였습니다. 방법이 떠올리지 않아서 아래의 글에서 규칙을 알게되었습니다. https://eunhee-programming.tistory.com/99

코딩테스트 준비 - 백준 1011번 풀이/자세한 풀이(파이썬)

가중치를 1 ,22, 333, 4444,  5555,  6666 ... 다음과 같이 더하면 됩니다.

T = int(input())

def distance(cost):
    count = 0  # 이동 횟수
    move = 1  # count별 빈도수
    move_plus = 0  # 이동한 거리의 합
    while move_plus < cost :
        count += 1
        move_plus += move  # count 수에 해당하는 move를 더함
        if count % 2 == 0 :  # count가 2의 배수일 때
            move += 1  
    
    return count
    
    

for _ in range(T):
    x, y = map(int, input().split())
    print(distance(y-x))