백준 1789번: 수들의 합 (파이썬)

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

1789번: 수들의 합

 

문제

 

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

 

입력

 

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

 

출력

 

첫째 줄에 자연수 N의 최댓값을 출력한다.

 

풀이

 

처음 풀이는 S에서 1부터 n까지 차례대로 빼면서 남은 수가 n보다 작거나 같다면 n에 남은 수를 더하여 빼줌으로써 n의 최댓값을 구했다.

하지만 이 풀이는 시간 초과 에러가 발생했다.

처음 풀이의 아이디어의 핵심은 1부터 n까지의 합을 빼고, 남은 수가 n보다 작거나 같으면 남은 수를 n에 더해서 빼는 것이었다.

따라서 합 공식을 사용하면 시간 복잡도를 줄일 수 있을 것이라고 생각했고, 이를 적용시켜 n의 최댓값을 구하였다.

이 풀이는 문제 없이 통과하였다.

 

소스 코드

 

s = int(input())

for i in range(1, s+1):
    sum = i*(i+1)/2
    if s - sum <= i:
        print(i)
        break