[백준/파이썬] 1789번 수들의 합 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1789번 수들의 합
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

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

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

print(int(((1+int(input())*8)**.5-1)/2))

설명

우선 문제의 알고리즘 분류는 이진 탐색이지만, 좀 더 간단하고 복잡도가 최소인 방법이 따로 있습니다.

바로 수학적으로 푸는 방법입니다.

서로 다른 N개의 자연수의 합이 S일때, N의 최대값은 당연히 서로 다른 N개의 자연수가 가장 작은 수들로 구성되어 있겠죠? 이는 1부터 X까지의 합에서 필요없는 수 몇 개를 버린 것과 동치입니다.

즉, n(n+1)/2 <= S 라고 할 수 있습니다.

이 식을 정리해보면, n^2 + n - 2S <= 0 입니다. 이는 이차 부등식을 푸는 방식으로 풀 수 있습니다.

근의 공식을 적용해보면 n은 -1 ± √(1+8s) 사이의 값이 됩니다.

우리는 이 중 최대의 값이 필요하므로, √(1+8s) - 1을 사용하면 됩니다.

---

• 백준 문제풀이 전체 목록 보기

---