백준 1789번: 수들의 합 python 풀이 및 정답 코드

문제 링크

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

1789번: 수들의 합

 

 

문제 설명

문제

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

입력

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

출력

첫째 줄에 자연수 N의 최댓값을 출력한다.

 

 

문제 풀이

이분탐색 문제이다.

포인트는
1. 가우스 법칙에 따라 n까지의 합은 n*(n+1)/2 이므로 2*S의 제곱근을 right 값으로 잡는다.
2. left = 1로 두고 이분탐색 진행

 

 

코드

import math

S = int(input())

left = 1
right = int(math.sqrt(2*S))
while(True):
    mid = int((left+right)/2)
    if right - left < 0:
        print(mid)
        break
    if mid * (mid+1)/2 <= S:
        left = mid + 1
    else:
        right = mid-1

 

 

결과

통과

 

 

다른 사람의 코드

 

 

 

리뷰

1, 3, 6, 10 같이 딱 떨어지는 경우를 생각 안해줘서 한번 틀렸다ㅎ

무작정 제출하지 말고 충분히 테스트 해 본 후 제출하는 습관 필요...