[EASY][Greedy][BinarySearch] 백준 1789번 : 수들의 합

[jeongabae]

1년 전에 푼 문제...

실버5

시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 -- | -- | -- | -- | -- | -- 2 초 | 128 MB | 34602 | 14081 | 12045 | 42.281%

문제

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

입력

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

출력

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

예제 입력 1 복사

200

예제 출력 1 복사

19

출처

• 문제를 만든 사람: author5
• 데이터를 추가한 사람: kangwh0617, newton08, upple1

알고리즘 분류

• 수학
• 그리디 알고리즘

내 풀이1 : 이진탐색 이용 풀이(이게 빠름)

s = int(input())
ans = 0
start, end = 0, s

while start<=end:
    mid = (start+end)//2
    if mid*(mid+1)//2 <=s: #1부터 mid까지의 합이 n보다 작거나 같으면
        ans = mid
        start = mid+1
    else:
        end = mid-1
print(ans)

200이 입력으로 들어왔을 때 1~20까지 더하면 210 1~19까지 더하면 190 그래서 1~18까지 더한 후, 200에서 모자란 수를 마지막으로 더하면 서로 다른 19개의 자연수의 합으로 200을 만든 것.

내풀이2

s = int(input())
tot = 0
N = 0
while s > tot + N:
    N += 1
    tot += N

print(N)

1부터 더해가며 만든 합(tot)이 s를 초과하기 전까지의 숫자가 N의 최댓값! 이를 적용하면 다음과 같다.

문제의 예시를 통해 알아보면.. 1(1번째 숫자) + 2(2번째 숫자) + 3(3번째 숫자) + 4(4번째 숫자)+ .... + 17(17번째 숫자) + 18(18번째 숫자) + 19(19번째 숫자)= 190 ->총 19개 190+20=210 ->총 20개 그래서 20을 더하면 안됨..! 19번째 숫자를 19가 아닌 29로 해서 더하면 200이 나온다. 1(1번째 숫자) + 2(2번째 숫자) + 3(3번째 숫자) + 4(4번째 숫자)+ .... + 17(17번째 숫자) + 18(18번째 숫자) + 29(19번째 숫자)= 200 ->총 19개 이런 식으로해서 다른 s가 들어와도 자연수 N의 최댓값을 구할 수 있다. ( 200이 입력으로 들어왔을 때 1~20까지 더하면 210 1~19까지 더하면 190 그래서 1~18까지 더한 후, 200에서 모자란 수를 마지막으로 더하면 서로 다른 19개의 자연수의 합으로 200을 만든 것. )