#백준#11659#부분합#python#시간초과

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

11659번: 구간 합 구하기 4

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

예제 입력 1 

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력 1 

12
9
1

처음에 리스트의 sum으로 작성한 코드

import sys
n = list(map(int, sys.stdin.readline().split()))
m = list(map(int, sys.stdin.readline().split()))
for i in range(n[1]):
    t = list(map(int, sys.stdin.readline().split()))
    ans = sum(m[(t[0]-1):(t[1])])
    print(ans)

결과 : 시간초과

누적합을 이용하지 않고 단순 합계를 이용한다면 시간초과 오류가 나게 된다.

구간합을 구하는 시간복잡도는 O(n)이고 m번동안 수행을 하게 된다면

시간복잡도는 O(nm)이 되서 시간 안에 통과가 불가능하다 

- 수정 

import sys
n = list(map(int, sys.stdin.readline().split()))
m = list(map(int, sys.stdin.readline().split()))
for i in range(n[1]):
    t = list(map(int, sys.stdin.readline().split()))
    lllist = [0]*(n[0]+1)
    for k in range(1, n[0]+1):
        lllist[k] = lllist[k-1]+m[k-1]
    print(lllist[t[1]]-lllist[t[0]-1])

결과 : 시간초과

구간 합을 미리 구해놓지 않고 구간을 받을때마다 합을 새로 구해서 연산이 늘어났다

이미 m 리스트는 받았기 때문에 구간 합을 먼저 구해놓고 나서 

구간을 받을때 서치만 하는 방향으로 코드를 수정했다

import sys
n = list(map(int, sys.stdin.readline().split()))
m = list(map(int, sys.stdin.readline().split()))
lllist = [0]*(n[0]+1)
for k in range(1, n[0]+1):
    lllist[k] = lllist[k-1]+m[k-1]
for i in range(n[1]):
    t = list(map(int, sys.stdin.readline().split()))
    print(lllist[t[1]]-lllist[t[0]-1])

구간 합

[ a, b, c, d, e] 리스트가 있으면

누적 합의 리스트는

[0, a, ab, abc, abcd, abcde] 

길이가 1개 늘어난 리스트가 된다

2번부터 4번까지 bcd 합을 구하고 싶으면

미리 구해놓은 구간합 리스트에서

abcd - a 의 값을 찾는 방법으로 구할수 있다

1번부터 3번까지 abc 합은 

abc는 abc - 0 의 값이 어디있는지 연산이 필요없이 찾기만 하면 된다