백준 / 1789 / 수들의 합

문제

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

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

접근방식

처음에 너무 어렵게 생각해서 좀 막혔던 것 같습니다. 가장 많은 자연수의 합으로 구성되려면 무조건 1부터 차례대로 더하면서 S가 넘어서는 시점에서의 숫자 개수를 알아내면 되는 것이었습니다.

(풀이)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

S = int(sys.stdin.readline())
cnt = 0
total = 0

while True:
    if total == S:
        break
    elif total > S:
        cnt -= 1
        break
    cnt += 1
    total += cnt

print(cnt)

회고

혹시, 타임아웃때문에 미리 계산한다거나 수식을 이용해야하나 생각했었는데, O(N)정도 되는 사이즈는 일단 나이브하게 접근해도 큰 문제는 없어보입니다.