문제
정수 a부터 b까지의 합을 구하라.
입력
테스트 케이스 수 T와 각 케이스에 정수 a, b가 주어진다.
출력
각 케이스마다 Scenario #k: 후 합을 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 1 100 -3 5 | Scenario #1: 5050 Scenario #2: 9 |
풀이
가우스 등차수열 합 공식을 적용한다.
- a부터 b까지의 합은
(b - a + 1) * (a + b) / 2이다 - 정수 나눗셈으로 정확하게 계산한다
핵심 아이디어: 가우스의 등차수열 합 공식 n(첫항+끝항)/2로 O(1)에 계산한다.
코드
for i in range(int(input())):
a, b = map(int, input().split())
res = (b - a + 1) * (a + b) // 2
print(f"Scenario #{i+1}:")
print(f"{res}\n")복잡도
- 시간: O(T)
- 공간: O(1)