[백준] 1789번: 수들의 합 - Python

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

문제가 재미있어서 가지고 왔습니다.

엄청 간단한 문제인데, 정작 아이디어를 떠올리는데 오래 걸렸어요.

여기서 아이디어가 간단하게 나온 분들도 있을 것 같은데 

저는 그냥 i부터 i+N개까지 다 더한게 200이 되면 되는거 아닌가? 라는 단순한 생각을 했습니다.

그런데, 코드를 짜고 200을 넣고 해보니, N = 16이 최대 값이더라구요?

거기에 i를 증가시켜야하고 덧셈의 결과도 계산해야하니, 시간복잡도가 O(N^2)이 나올 것 같아서 문제의 S의 범위를 보면 

절대 불가능한 코드였습니다.

고민을 조금 하다보니, 1 ~ N까지의 자연수의 합 공식이 떠올랐고, 

1 ~ N까지의 자연수의 합 = n(n+1)/2

​n(n+1)/2 ≤ S^2 을 만족하면 무조건 정답 아닌가? 라는 생각에 코드를 만들었습니다.

import sys

s = int(sys.stdin.readline())
n = 0
while True:
    n += 1
    if n**2 + n - 2*s > 0:
        break

print(n-1)

실제로 200을 예시로 들어보면

1부터 19까지 모두 더하면 190인데, 19를 29로 교체해서 더한다면 200을 완성시키고 

N의 최대값을 구할 수 있습니다.