A<=B 일때 A ~ B 까지의 합은 ('1 ~ B'의 합) - ('1 ~ A-1'의 합) 과 동일하다.
1~x 까지의 합을 psum[x] 에 저장하고 A~B의 합을 psum[B]-psum[A-1] 로 계산하면
A ~ B의 합을 시간복잡도 O(1) 에 구할 수 있다.
처음에는 break 처리를 하지 않고 전부 순회했는데, 이 때 시간초과가 발생했다.
더 이상 확인해도 의미가 없는 시점에 break를 추가하였더니 시간초과가 사라지고 통과되었다.
def solution(n):
MAXN = 10000
psum = [0 for _ in range(MAXN+1)]
psum[0] = 0
for i in range(1, MAXN+1):
psum[i] = psum[i-1]+i
answer = 0
for st in range(0, n+1):
for ed in range(st+1, n+1):
current = psum[ed]-psum[st]
if current > n:
break
if current == n:
# print(st, ed)
answer += 1
break
return answer