[백준] Sil4 | 이진탐색 | 1789 수들의 합 Python

[백준] Sil4 | 이진탐색 | 1789 수들의 합 Python

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

 

 

구상

두가지 방법으로 풀이했다.

1. 손구상 풀이 (greedy)
   • 내가 손구상한 풀이로도 가능했음. 답까지 모든 경우에 조건을 확인해야해서 더 오래걸리지만..
   • 이진탐색문제라고 해서 이진탐색으로도 풀었다
2. 이진탐색으로 한번 더 풀어보자

 

트러블 슈팅

• 이분탐색 시 다음 범위는 현재 중간값을 포함하지 않는 범위로 설정해줄 것!
• 숫자 합 계산에 sum(range()) 를 썼더니 시간초과 발생. 
  • 1~n까지의 합 = n(n+1)/2 임을 활용하자!

 

코드 - greedy

# v1 : greedy (60ms)
#       그리디 / 이진탐색 둘 다로 풀리는 문제
# TS : range 범위 경계값에 걸리는 경우 없는지 생각 잘하기

S = int(input())
answer = 0

add = 0
for i in range(1, S+1) :
    add += i

    #이번 숫자를 더했을 때 주어진 수보다 더 커졌다면, 이번 숫자를 더하지 않고 마지막 더한 수에 남은 수를 합한 수를 마지막으로 더한 경우가 답
    if S < add :
        answer = i-1
        break
    #이번 숫자를 더했을 때 주어진 수와 동일해졌다면, 이번 숫자까지 더한 경우가 답
    elif S == add :
        answer = i
        break

print(answer)

 

코드 - binary search

# v3 : 이진탐색..의 느낌을 더 살려서! (44ms)
# TS : 이분탐색 시 다음 범위는 현재 중간값을 포함하지 않는 범위로 설정해줄 것!

S = int(input())
answer = 0

start, end = 1, S #이진탐색의 left, right인덱스
while start <= end :
    #이진탐색
    mid = (start + end) // 2
    add = mid*(mid+1) // 2 #1~n까지의 합 = n(n+1)/2

    if S < add :
        end = mid - 1 # TS
    elif S == add :
        answer = mid 
        break
    elif add < S :
        start = mid + 1
        answer = mid

    
print(answer)

 

 

 

참고글

https://hose0728.tistory.com/85

백준 알고리즘 1789번 수들의 합 풀이 With Python