[백준/BOJ/알고리즘/파이썬(python)]#11441: 합 구하기[누적 합]

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

11441번: 합 구하기

처음에는 바로 합을 구해서 출력하도록 했는데 시간초과가 났다.

 

시간초과 코드

#11441 합 구하기
import sys
input = sys.stdin.readline

N = int(input())

A = []
A =list(map(int, input().split()))


M = int(input())


for k in range(M):
    i, j = map(int, input().split())

    sum = 0
    for x in range(i-1, j):
        sum += A[x]
        
    print(sum)

 

분류가 '누적 합'문제인 것을 보고 

미리 합을 다 구해놓은 리스트를 만들어놓고

누적끼리 인덱스에 맞춰 빼주는 로직으로 바꾸어 풀었더니 성공했다.

 

출력도 print가 아닌 stdout.write()로 바꾸고 컴파일러도 pypy3로 바꾸었다...

 

시간복잡도에 매우 센시티브하신 백준 https://www.acmicpc.net/blog/view/56 참고해두면 좋을 것 같다.

 

파이썬 코드

#11441 합 구하기
import sys
input = sys.stdin.readline

N = int(input())

A = []
A =list(map(int, input().split()))

ans = [0]*(N+1)

for k in range(N):
    ans[k] = ans[k-1]+A[k]

M = int(input())

for k in range(M):
    i, j = map(int, input().split())

    res = ans[j-1]-ans[i-2] 
    sys.stdout.write(str(res)+'\n')