[Python] 1789 수들의 합

📌 문제

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

📌 입력

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

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

가장 많은 자연수의 개수로 S를 찾아야 한다. 그렇다면 각 자연수들의 차이가 가장 적어야 가장 많은 자연수의 합으로 S를 구할 수 있다.

이 문제를 풀기 전에 1부터 n까지의 합을 생각해보았다.

n(n + 1) / 2 = k

예제가 200이어서 그 근사치를 구하기 위해 n = 19라고 했을 때 k = 190이다. 그리고 n = 20이라고 했을 때 k = 210이다.

n이 19라면, 1~19의 합인데, 여기서 1~18까지 더하고 19가 아닌 29를 더하면 200이 된다.

즉, 1부터 n까지의 합을 구하고 거기서 값을 살짝 수정하는 것이 답이 된다.

👨‍🏫 문제 풀이

📄 전체 코드

s = int(input())
n = 1

while True:
    if n ** 2 + n > 2 * s:
        n -= 1
        break
    n += 1

print(n)

s = int(input())
n = int((2 * s) ** .5)

if n * (n + 1) <= 2 * s:
    print(n)
else:
    print(n - 1)

☝ 시간 복잡도를 줄인 코드

근사치 n을 구해서 s를 도출한다.

📄 준비

s = int(input())
n = 1

1부터 n까지 더해보기 위해서 n을 설정

📄 풀이

while True:
    if n ** 2 + n > 2 * s:
        n -= 1
        break
    n += 1

print(n)

시그마를 통해서 합이 2 * s를 넘는 순간 n에서 1을 빼주고 반복을 탈출한다.

📌 총평

의외로 쉬웠다.