[백준] 11659번 구간 합 구하기 4: Python

문제 해결 포인트

가장 먼저 떠오르는 아이디어는 리스트에 N개의 수를 모두 넣은 뒤 split()와 sum()을 이용하는 방법일 것입니다. 그러나 sum()은 iterator를 이용하여 리스트의 원소를 하나하나 순회하면서 덧셈을 하기 때문에, M개의 입력의 각각에 대하여 sum()을 하게 된다면 시간복잡도는 O(MN)이 되어 시간초과가 발생합니다. 따라서 덧셈부분을 최적화해야하는데 여기에는 간단한 수학 지식이 사용됩니다.

바로 부분합을 빼면 일반항이 나온다는 사실인데 고등학교때 다들 한번쯤은 들어보셨을겁니다. 

 

https://calcproject.tistory.com/479

 

코드 작성

N개의 수를 입력 받으면서 S_0, S_1, S₂ ...를 차례대로 리스트에 넣어줍니다. 이후 M개의 케이스를 입력받으며 부분합끼리 빼서 일반항들의 합을 구합니다. 주의해야 할 점은 부분합 리스트의 가장 첫번째 원소는 0이어야 합니다. 부분합 리스트의 인덱스에 접근하기 때문에 인덱스 범위를 고려하여 코드를 작성합니다.

    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    numList = list(map(int, input().split()))
    subSum = 0
    sumList = [0]
    #시간복잡도 O(N)
    for i in numList:
        subSum += i
        sumList.append(subSum)

    #시간복잡도 O(M)
    for i in range(0, M):
        a, b = map(int, input().split())
        print(sumList[b] - sumList[a-1])