BACKJOON 1568번 ( 새 )

여기서 N이 최대 10⁹ 이니까 1,000,000,000 이다.

새들은 1부터 오름차순으로 반복적으로 증가하므로, 날아가는 새의 마리 수는 빠르게 증가한다는 것을 알 수 있다.

그럼 등차수열이기에 O(n²)으로 시간복잡도가 분류된다. 그렇기에 N이 큼에도 불구하고 단순하게 요구하는대로 풀 수 있다.예시입력이 14인 것을 보면, 1 2 3 4 에서 5마리의 새는 날아가지 못하니까(15가 됨) 다시  1부터 시작해서 1 2 에서 13이 되고 3마리의 새는 날아가지 못하고 다시 1이 되니까 1 2 3 4 1 2 1 이니까 총 7초가 걸린다.

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

while n != 0: # 모든 새가 날아갈 때까지
    if k > n:
        k = 1
    n -= k
    k += 1
    result += 1

print(result)

여기서 k는 1부터 출발을 하고, 입력된 숫자 'n'의 값이 0이 될 때까지, 즉 모든 새가 다 날아갈 때까지 반복한다. 순차적으로 증가하는 수 'k'를 이용해서 'n'에서 계속 빼는데, k가 n보다 커질 시, k는 다시 1로 재설정되면서 반복된다.

 

각 루프가 완료될 때마다 result 변수는 1씩 증가해서 총 몇 초가 걸리는지 확인할 수 있다.