수들의 합 ( 1789 번 )

1789번: 수들의 합

 

---

🧠 알고리즘

• 이진 탐색(Binary Search) + 수학적 합 공식 활용

 

✔️ 동작 방식

문제 핵심 아이디어

• 1부터 k까지 자연수 합 1 + 2 + ... + k = k * (k + 1) // 2
• 주어진 n 이하로 합을 만들 수 있는 최대 k를 찾는 것이 목표

주요 로직 요약

1. 입력 처리
   • n을 입력받음
2. 이진 탐색 수행
   • 구간 초기화: l = 1, r = n
   • mid = (l + r) // 2 계산
   • now_sum = mid * (mid + 1) // 2
     • 만약 now_sum <= n이면, answer = mid로 갱신하고, 더 큰 값을 탐색 (l = mid + 1)
     • now_sum > n이면, 범위를 줄여 탐색 (r = mid - 1)
   • l > r가 될 때까지 반복
3. 결과 반환
   • n 이하로 만들 수 있는 최대 k 출력

---

 

🧾 코드

import sys

def _main(n):
    """
        수학문제..
        서로 N개 자연수 합이 = S >> 일떄 N 최댓값
        1+2+3+4+.. <= S ( 1부터 더한 값이 무조건 많은 N을 가짐 )
        즉, n * (n + 1) // 2 <= S
    """
    l, r = 1, n
    while l <= r:
        mid = (l + r) // 2
        now_sum = mid * (mid + 1) // 2

        if now_sum <= n:
            answer = mid
            l = mid + 1
        else:
            r = mid - 1

    return answer
        

n = int(sys.stdin.readline().rstrip())
print(_main(n))

---

 

⏱️ 시간 복잡도

while l <= r : 이진 탐색 ( 로그 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 로그 시간 복잡도 ( O(log n) )