[SWEA][Python3] 4112. 이상한 피라미드 탐험

나의 풀이 :

def find(x):

low, high = 1, 141

mid = (low + high)//2

while (mid-1)*mid//2 >= x or x > mid*(mid+1)//2:

if x > mid*(mid+1)//2:

low = mid + 1

else:

high = mid

mid = (low + high)//2

return (mid, mid*(mid+1)//2 - x)

T = int(input())

for tc in range(1, T + 1):

a, b = map(int, input().split())

if a > b:

a, b = b, a

row_a, diff_a = find(a)

row_b, diff_b = find(b)

if diff_a > diff_b:

ans = (row_b - row_a) + (diff_a - diff_b)

else:

ans = max(row_b - row_a, diff_b - diff_a)

print('#{} {}'.format(tc, ans))

한마디 :

이진 탐색 + 등차수열의 합 으로 접근하였다.