백준 1789 : 수들의 합

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

1789번: 수들의 합

 

해결 방법 : 이분탐색

• 만약 N이 sum(range(n)) <= N < sum(range(n+1))을 만족한다면, 답은 n이다.
  • ex. N은 14이면 sum(range(4))가 10, sum(range(5))는 15 이므로 위를 만족하는 n은 4인데, 이 때 range(4) = [1,2,3,4]에서 마지막 자연수 '4'대신 N과 sum의 차이인 '4'만큼 더 큰 자연수 '8'을 포함시키는것이 최선일 것이다.
• 물론 sum(range()) 가 아닌, 등차수열 합 공식을 사용!

import sys
input = sys.stdin.readline

def solution(N):
    mn, mx = 1, 1000000

    while mn < mx - 1:
        mid = (mn + mx) // 2
        if (mid * (mid + 1)) / 2 <= N:
            mn = mid
        else:
            mx = mid
            
    return mn

if __name__ == '__main__':
    N = int(input())
    result = solution(N)
    print(result)