[문제 풀이] 백준 1011

해결 과정

찐 수학 문제임 ㅋ 수학 문제 하나 풀어볼까 해서 푸는데, 오랜만에 고등 수학 다시 보고 옴 ㅋㅋ 등차수열의 합 오랜만~

일단 이동 횟수의 최솟값을 찾으라는데, 규칙을 찾았음. 

이동 횟수를 최소로 하는 경우	거리 k	이동 횟수 r
1	1	1
1+2+1	4	3
1+2+3+2+1	9	5
1+2+3+4+3+2+1	16	7

이런 식으로 최소가 되도록 하는 규칙을 찾으며 공식을 도출함.

 

y-x를 거리 k 라고 했을 때, 이동 횟수의 최솟값을 r이라고 하자.

r ==2√k - 1

다만, 이것은 r이 정수가 나올 때만 유효하고, 정수가 나오지 않을 때는 따로 생각해봐야 함.

1 2 3 4  여기서 2는 1.xxx 3은 2.xxx 가 나왔는데, 이를 보고 올림을 하면 되겠다고 생각함.

4 5 6 7 8 9 이 경우도 딱 반절씩 나눠지길래(5, 6 과 7, 8)

 

 

나의 풀이

import math

def solution(x, y):
    k = y - x
    tmp = 2 * math.sqrt(k) - 1
    if tmp.is_integer():
        return int(tmp)
    else:
        return int(math.ceil(tmp))

T = int(input())
for i in range(T):
    a, b = map(int, input().split())
    print(solution(a, b))