[백준/Python] 24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4

단계별로 풀어보기 > 단계 11: 시간 복잡도 > 242645번

#24265: 알고리즘 수업 - 알고리즘의 수행 시간 4
n = int(input())
sum = 0
for i in range(n):
  sum = sum + i
print(sum)
print(2)

#다른 방법
print(n*(n-1)//2)
print(2)

 

문제의 반복문을 봅시다. 이중 반복문이 첫 번째 반복문의 영향을 빋아, n-1부터 1까지 반복합니다. 따라서 for문으로 합산을 구해도 되고, 등차수열의 합으로 계산해도 됩니다. 식이 $n(n-1)/2$이므로 최고차항의 차수는 2가 됩니다.