당연히 i부터 j까지 for문을 돌리는 건 시간초과가 날 것이고 문제의도에 맞지 않을 것이라 생각했다. 중딩? 때 배운 수열의 합 S를 잘 활용하면 되겠다 생각은 했는데,,, 또 찬찬히 생각하지 않고 손은 검색을 향했다...
아이디어
- 중학교? 때 배운 수열의 합 Sn을 떠올렸다.
- An = Sn - Sn-1을 말이다.
- 이 아이디어에서 착안해보면 i~j까지의 합은 Sj - Si-1임을 알 수 있다.
- 즉, 구하고자 하는 i번째 수부터 j번째 수까지 합은 Sj - Si-1를 이용해서 빠르게 출력해보자.
- 따라서 우리는 Sn 값을 알아야 하므로 얘네를 리스트에 저장해 두자. 즉, 1부터 n까지의 합은 리스트에 저장하면 되겠다.
코드
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
num = list(map(int, input().split()))
sum = [0]
for i in range(1, N+1):
sum.append(sum[i-1]+num[i-1])
for _ in range(M):
i, j = map(int, input().split())
print(sum[j]-sum[i-1])- 문제에서 인덱스 i부터 j까지가 아닌, i번째부터 j번째까지라고 했다.
- 인덱스는 0~N-1까지인데, i,j는 1~N까지의 수다.
- 그래서 인덱스의 범위에 벗어나지 않도록 맞추기 위해 for의 범위를 조정하거나 i를 그대로 쓰지 않았다.
- 먼저 N개의 리스트는 그대로 0부터 N-1까지의 인덱스에 수를 담았다.
- sum은 0 인덱스에는 0을 담아, 1 인덱스부터 N 인덱스까지 num의 1번째수(0인덱스)부터 N번째수까지의 합을 담았다.
1번째 for문
- Sn = Sn-1 + An임을 이용해서 1~n까지의 합을 n+1번째 인덱스에 담았다.
2번째 for문
- Si~j = Sj - Si-1임을 이용해서 i번째 수부터 j번째 수까지 합을 구해 출력했다.
결과
