[백준 11561] 징검다리

초기 코드

import sys
input = sys.stdin.readline

n = int(input())

for _ in range(n):
  target = int(input())

  sum = 0
  i = 1
  count = 0
  while(sum <= target):
    sum += i
    i += 1
    count += 1

  print(count - 1)
    

너무 쉽게 풀려서 사실 의심을 하긴 했다. 그래도 이 정도면 꽤나 빠를거라 예상했는데...

입력값의 함정이 있었다. 바로 N의 범위가 10^16 까지라는 것...

더 빠르게 처리해야한다.

최종 코드

import sys
input = sys.stdin.readline

n = int(input())

for _ in range(n):
  target = int(input())

  start = 1
  end = 10 ** 9
  answer = 0

  while(start <= end):
    mid = (start + end) // 2

    # 처음부터 절반
    if((1 + mid) * mid // 2 <= target):
      answer = mid
      start = mid + 1
    else:
      end = mid - 1
    
  print(answer)

이분 탐색을 생각해야 한다.

1부터 시작해서 어디까지 더해도 되는지를 찾는데, 이걸 범위를 절반씩 쪼개 가면서 찾는 것이다.

end를 정한 기준은 1부터 10^9까지 등차수열의 합으로 구했을 때 10^16을 넘어가기 때문에 선정했다.

등차수열의 합을 이용하여 이분탐색 범위를 찾는 것이 상당히 어려웠다... 효율적인 알고리즘을 위해 많이 고민해야 할 것 같다!