수들의 합

백준 1789

• 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?
• 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
• 첫째 줄에 자연수 N의 최댓값을 출력한다.

입출력

입력	출력
200	19

---

접근 방식

: 1부터 n까지의 합인 n*(n+1)//2 공식 활용

알게된 점

1부터 n까지 모두 더하는 것이 n을 최대로 만들 수 있다.
1부터 19까지의 합은 190이고 1부터 20까지의 합은 210이다. 200을 만들고, n이 최댓값일 수 있는 방법은 1부터 20까지의 수 중 하나(10)를 빼는 것이다.
따라서 1부터 i까지의 합이 입력값이면 i를 출력하면 되고, i보다 작다면 i-1을 출력하면 된다.

코드

s = int(input())

n = 1
while n*(n+1)//2 <= s:
    n += 1
print(n-1)

이분탐색

m = int(input())

s, e = 1, m
while s<=e:
    mid = (s+e)//2
    if (mid*(mid+1))//2 > m:
        e = mid-1
    else:
        ans = mid
        s = mid + 1
        
print(ans)