[Baekjoon]백준 11659 구간 합 구하기 4(실버 3) - Python

문제설명

문제는 간단하다 i번째 수부터 j번째 수까지의 합을 구하면 된다

누적합 알고리즘에 대해 알고있다면 충분히 쉽게 해결할 수 있다

이전에 누적합 알고리즘으로 푼 문제가 있기 때문에 간단하게만 설명하자면 

이전까지의 합을 미리 계산해 저장해 두고, 이를 활용하여 특정 구간의 합을 빠르게 구하는 알고리즘이다

즉, sum[i+1] = sum[i] + ~~ 가 되는 것이다

이를 활용하여 누적합이 계산된 리스트를 하나 만들어 저장해두고, i-1번째의 합을 빼주면 정답을 출력하게 된다

(i부터 j까지의 합을 구하려면 i-1을 해주어야하는데, 만약 그대로 i번째의 합을 빼게 된다면

그 합에는 i의 index의 값도 포함되어있기 때문에 i번째부터의 합이 되지 않는다!!)

list_num, sum_num = map(int, input().split())
ls = list(map(int, input().split()))
sum_ls = [0] * (list_num + 1)

for i in range(list_num):
    sum_ls[i + 1] = sum_ls[i] + ls[i]

# print(sum_ls)
for _ in range(sum_num):
    start_index, end_index = map(int, input().split())
    print(sum_ls[end_index] - sum_ls[start_index-1])

그런데...시간초과가 발생하였다 처음에 서버가 이상한 줄 알고 5분 정도 있다가 다시 올려도 그대로 이길래

다른 분들의 블로그를 찾아보아도 같은 방식임을 알 수 있었다

그렇게 이유를 찾던 도중...import sys를 사용한 코드를 발견하였고 이를 사용하니 시간초과가 발생하지 않았다

import sys

list_num, sum_num = map(int, input().split())
ls = list(map(int, sys.stdin.readline().rstrip().split()))
sum_ls = [0] * (list_num + 1)

for i in range(list_num):
    sum_ls[i + 1] = sum_ls[i] + ls[i]

# print(sum_ls)
for _ in range(sum_num):
    start_index, end_index = map(int, sys.stdin.readline().rstrip().split())
    print(sum_ls[end_index] - sum_ls[start_index-1])