[BOJ] 1789번 : 수들의 합

🔒 문제

⌨ 입력

🖨 출력

📚 예제

📌 풀이

문제에서 주어진 숫자 S를 서로 다른 자연수들을 N개 더해서 만드는데 N의 개수의 최댓값을 구하는 것이다.

쉽게 생각하면 작은 수인 1부터 2, 3,,, 차례로 더해가면 N이 최대가 된다 는 것을 생각하면 된다.

그래서 생각해낸 풀이 방법이 등차가 1인 등차 수열을 생각해서 등차수열의 합 공식을 사용하는 것이었다.

temp = 1 + 2 + 3 +,,, + n까지 더한 값은 temp = n * (n + 1) / 2 로 구할 수 있다.

이 temp 값이 S값 커졌을 때의 n 값에서 1을 뺀 것이 바로 답이다.

1을 빼주는 이유는 200을 예를 들어서 설명하겠다

200에 가장 가까운 200보다 큰 temp 값은 n이 20인 210이다.

temp가 210일 때 n값은 20이고 그러면 그 전값인 n값이 19인 경우에 temp 값은 190이다.

서로 다른 수를 써야하기 때문에 200이 되기위해서 190에 10을 더할 수는 없다. 왜냐하면 10은 앞에서 사용했기 때문이다.

대신 마지막 수인 19에 10을 더해줘서 1 + 2 + 3 + ... + 18 + 29로 해서 총 19개의 수를 더해서 마무리한다.

정리하자면, 등차수열의 합 공식인 n*(n + 1)/2를 이용해서 그 합인 temp가 S에 가장 가깝지만 S 보다 작은 수 n을 구해주면 끝이다.

🔑 python 코드

# 수들의 합
import sys
input = sys.stdin.readline
S = int(input())
temp = 0
n = 0 
while(temp <= S):
    n += 1
    temp = int(n*(n + 1) / 2)

print(n - 1)