[BOJ] #1568 - 새

1568번: 새

 

 

** 문제 유형

• 순차 탐색

 

** 풀이

1. N이 최대 1,000,000,000
   • 시간 복잡도 O(n^2)
2. K가 반복적으로 증가하므로, 날아가는 새의 마리 수는 빠르게 증가
   • 등차수열로 실질적인 시간 복잡도는 약 O(√n)
3. 따라서 문제에서 요구하는 대로 단순히 구현

 

n = int(input())
k = 1
cnt = 0

while n > 0: # 모든 새가 날아갈 때 까지
    if n < k:
        k = 1
    
    n -= k
    k += 1
    cnt += 1
    
print(cnt)