백준 알고리즘 1789번 수들의 합(python)

단순한 방식

입력보다 커지기 전까지 1, 2, 3, 4, 5... 를 계속 더하다가 마지막으로 더해진 값을 출력해주면 된다.

1부터 n까지 수의 합 = n * (n+1) // 2

n = int(input())
i = 1
while i * (i+1) // 2 <= n:
    i += 1
print(i-1)

 

이분 탐색

마찬가지로 1부터 n까지 수의 합 = n * (n+1) // 2 인 점을 이용하면 쉽게 해결할 수 있다.

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