BOJ_1789 수들의 합

• TOC {:toc}

이 글은 백준 온라인 저지의 1789번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.03.25

N = int(input())
s = 0
i = 1

while True:
    s += i
    if s > N:
        break
    i += 1
print(i - 1)

아이디어 & 풀이

서로 다른 N개의 자연수를 더해서 주어진 값 S를 만들 때 N이 최댓값을 가지려면 최대한 작은 값의 수를 더해나가야 한다.

• 그러므로 $1 + \cdots + N \le S \lt 1 + \cdots + N + 1$인 N을 출력하면 된다.

참고 답안

# S = int(input())
# n = (-1 + sqrt(1+8S)) / 2
#   = ((8S+1) ** 0.5 - 1) / 2
# 더한 수의 개수는 [n] 이므로 int(n)을 출력
print(int(((8 * int(input()) + 1) ** 0.5 - 1) / 2))

아이디어 & 풀이

등차수열의 합을 나타내는 식을 이용해서 구현했다.

$$ S = {n(n+1) \over 2} = {n^2+n \over 2} \ n^2+n-2S = 0 \ n = {-1 + \sqrt{(1 + 8S)} \over 2} $$

S가 N까지의 합보다 ‘크’거나 같기 때문에 $\text{N = n.xxx}$ 이므로 $N = [n]$이다. 그러므로 구한 값에 int를 취해 소숫점 아래를 버려도 괜찮다.