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

티스토리 메뉴 펼치기 댓글수0

프로그래밍/삼성 SWEA

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

snoopybox
댓글수0

나의 풀이 :

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))


한마디 :

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

맨위로

https://www.snoopybox.co.kr/2017

신고하기