[Python] 백준 8393번_합

문제 

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

8393번: 합

 

코드

cnt = int(input())
print(sum(i for i in range(1,cnt+1)))

풀이 

간단하게 풀이가 가능해 보여서 직관적으로 풀었다. 이럴경우 시간 복잡도는 O(n).

 

✔ 하지만 수학적으로 접근하면 1~n 까지의 합은 n(n+1)/2 즉, (n^2 + n)/2 로 한번의 계산으로 도출 가능하며, 이때 시간 복잡도는 O(1)로 대폭 감소한다.

 

✔ 문제를 풀이할 때 여러 방향으로 생각해보자.

다른 풀이 

 출처: https://www.acmicpc.net/source/13249601

n = int(input())
print((n**2+n)//2)