[Python] 백준 #1789- 수들의 합

문제

---

 

1789번: 수들의 합

코드

---

My answer

import sys
input=sys.stdin.readline

n=int(input())
a=1
answer=0
while(1):
    answer+=a
    if(answer>n):break
    a+=1
print(a-1)

import sys
input=sys.stdin.readline
N=int(input())

s,cnt=0,0
while(1):
    cnt+=1
    s=int(cnt*(cnt+1)/2)
    if(s>n):
        break
print(cnt-1)

Another answer

import sys
input=sys.stdin.readline


n = int(input())
left,right = 1,n

while left <= right:
    mid = (left + right) // 2
    if mid * (mid + 1) // 2 <= n:
        answer = mid
        left = mid + 1
    else:
        right = mid - 1
print(answer)

풀이

---

이번 문제는 여러가지 방법으로 풀 수 있는 방법이었다. 

우선 문제자체는 간단했는데 메모리초과나 시간초과가 나는 문제였다.

우선 3가지 방법 모두 아이디어는 똑같다. N개의 자연수를 뽑았을 때 주어진 숫자가 도기 위한 최대 N의 개수는 수가 가장 많아야하기 때문에 그리디 적인 접근으로 그냥 작은 것들을 최대한 많이 더하다가 마지막에 남는 숫자를 넣어주면 됐다.

예시에 있는 200의 경우 그냥 1~18까지 더해서 171까지 만들고 29를 더해서 200을 만들면 총 19개를 사용한 것이다. 여기서 1~19까지 더하면 190이 되서 나머지가 10인데 10은 이미 더했기 때문에 서로다른 숫자 N개라는 조건에 위배되므로 18까지 더하는 것이 맞았다. 

첫번째 방법은 무식하게 1부터 순서대로 더하는 것이다. 1부터 순서대로 더하다가 n이 넘으면 멈추면 되는데 여기서 N=200일 때를 예시로 들면 아까의 경우 1~18까지 더하면 171, 19까지 더하면 190, 20까지 더하면 210 따라서 20에서 멈추게되는데 여기서 바로 전 19가 19까지 더하라는 것을 의미하는게 아니라 19전 18까지 더하고 나머지 1을 충족시키는 숫자 총 19개를 의미하는 19가 답이된다.  따라서 그냥 넘을때 멈추고 -1해주면 답이랑 동일시된다.

두번째 방법은 똑같은 아이디어(N이 넘을 때 멈추고~)를 가지고 푸는 방법인데 수열의합을 이용한 것이다.

1~N까지의 합은 가우스의 등차수열의 합에서 (등차수열의 합) = {(첫 항 + 마지막 항) * (항의 개수)} / 2 이라는 공식이 있다. 따라서 위와 똑같지만 직접 하나 하나 더하는 것이 아니라 저 식을 이용하여 합을 더한다는 것에만 차이가 있다. 

마지막 방법은 이분탐색으로 해결하는 방법이다. 재차말하지만 똑같은 아이디어로 하는데 1씩 위의 가우스공식도 이용해서 푼 방법으로 시작과 끝을 정하는데 이 끝을 두번째 방법처럼 무작정 늘려가는 것이 아니라, 이분탐색을 통해서 더 빠르게 접근하는 것이다. 이분탐색의 전형적 코드와 가우스 공식을 병합하면 된다.