[python] 1~N까지의 합, N~M까지의 합구하기

1부터 N까지의 합

내장함수 sum() 사용

sum(range(n+1))

✅ 시간 복잡도: $O(1)$
✅ 공간 복잡도: $O(N)$

▪ n이 커질 경우에 꽤 많은 메모리를 소모할 수 있다.

가우스의 공식 사용

S = 1 + 2 + 3 + 4 + 5
S = 5 + 4 + 3 + 2 + 1

2S = (n+1) * n개

S = n * (n+1) // 2

✅ 시간 복잡도: $O(1)$
✅ 공간 복잡도: $O(1)$

N부터 M까지의 합

가우스의 공식을 응용하여,
2S = (n + m) * (m-n+1)개

S = (n+m) * (m-n+1) // 2

# n, m의 대소관계가 정해져있지 않은 경우
(n + m) * (max(n,m) - min(n,m) + 1) // 2