99클럽 코테 스터디 2일차 TIL + 이분탐색

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

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n = int(input())
    start = 0
    end = n
    result = 0
    while start <= end:
        mid = (start+end) // 2 # 밟을 수 있는 징검다리 수
        if mid * (mid+1) // 2 <= n:
            start = mid + 1
            result = mid
        else:
            end = mid - 1
    print(result)

• 징검다리를 1개, 2개, 3개, ... 1 차이로 건너야 최대한 많은 징검다리 수를 건널 수 있다.
• 반드시 n번째 징검다리는 밟아야 하므로 1 + 2 + 3 + .... 가 n보다 작거나 같아야한다.
• 등차수열의 합을 구하는 공식 : n(n+1) / 2
• mid가 우리가 구하는 target 값(최대한 많이 밟을 수 있는 징검다리 수)

• n의 최댓값이 10^16 으로 매우 크므로 완전탐색이 아닌 이분탐색을 고려할 수 있는 방법이라고 한다.