[BOJ] Python 백준 징검다리(11561)

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

 

기본적인 조건인 최대한 많은 징검다리를 밟는다는 것은 최소한 짧게 뛰어야 많이 밟게 됌

즉, 1 + 2 + 3 + 4 + 5 + 6 .... + N 이런식으로 뛰어야 최대로 밟게된다.

 

위 공식은 등차 수열이므로 

SUM = N(N+1) // 2로 정리할 수 있다.

 

즉, 결과 값인 SUM이 N을 넘지 않는 선에서 제일 가까운 SUM 값에 대한 middle이 최대로 밟을 수 있는 값이다.

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())
    
    result = 0
    start = 0
    end = N
    
    while start <= end:
        
        middle = int((start + end) / 2)
        
        if int((middle*(middle+1))/2) <= N: # 등차수열 합 공식
            start = middle + 1
            result = middle
            
        else:
            end = middle - 1
            
    print(result)