수들의 합 - 백준 1789번

서로 다른 N개의 자연수들의 합 S가 주어졌을 때 N의 최대값을 구해야한다.

N에 속하는 자연수들을 하나하나 구하는 과정은 굉장히 복잡하겠지만, N의 최대값을 구하는 과정은 간단하다.

 

자연수들의 집합 N에 속하는 자연수들을 1, 2, 3, ... 처럼 점점 작은 것부터 커진다고 생각한다.

1부터 하나씩 커져가며 합해진 합계가 S와 우연히 같아질 수도 있고 달라질 수도 있다.

우연히 같아질 경우는 생각하기 쉬우니 넘어가고, 달라질 경우에 대하여 생각해보자.

점점 커져가는 합계가 S에 근접하여 처음으로 음수가 되는 때가 있을 것이다. 

이 때까지 수를 하나씩 샌 후 1을 빼주면 그 수가 N의 최대값이 된다.

왜냐하면 점점 커져가는 합계가 S에 근접하여 처음으로 음수가 되기 직전 앞에서 더해왔던 자연수들 중 몇개를 골라 자연수의 합인 S가 되도록 임의로 만들어주면 되기 때문이다.

 

n = int(input())

# 자연수 개수 카운트
num = 0

# 1부터 점점 더할 합계
result = 0

while n>=num:
    result+=num
    num+=1
    #주어진 S의 값에 1부터 점점 커져가는 자연수를 계속 빼준다.
    n -= num
if n<0:
    print(num-1)
else:
    print(num)

 

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

1789번: 수들의 합