백준-11659(파이썬)

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

11659번: 구간 합 구하기 4

문제생각

굉장히 쉽게 생각하였습니다.

입력을 받고 리스트 슬라이싱을해서 sum() 연산만 하면 된다고 생각했고 그런 방식으로 코드를 구성하였습니다.

그런데 시간초과가 발생하였습니다!! 

 

알고보니 리스트 슬라이싱의 시간복잡도가 꽤 높았던 것입니다. 무려 O(k)!!!

여기서 k는 슬라이싱을 해야하는 원소의 개수입니다.

이 슬라이싱 작업을 최대 10만번 해야했고 sum 연산까지 실행해야 했으니 1초의 시간제한으로는 시간초과가 나는 것이

당연했습니다...

 

그래서 생각을 해보았습니다. 슬라이싱과 sum() 연산을 하지 않는 방법...

 

문득 떠오른 생각이 

 

"구간의 합을 구하는 것이면 구간 끝까지 모두 더한 값에서

구간 시작 값까지 모두 더한 값을 빼면 그 구간의 합이 되지 않을까?"

 

였습니다.

 

그래서 아래와 같이 문제를 해결하였습니다.

 

1. 숫자 리스트의 누적합 리스트를 생성한다. 
2. 구간 끝까지의 누적합 - 구간 시작까지의 누적합 = 구간의 누적합
3. 구간 시작이 1이라면 구간 끝까지의 누적합이기에 sum_list[j]를 출력
4. 시작과 끝이 동일하다면 그냥 해당 인덱스의 숫자를 출력

 

문제코드

import sys
input=sys.stdin.readline

n, m=map(int, input().split())
num=list(map(int, input().split()))
sum_list=[0]
for i in range(n):
    s=sum_list[i]+num[i]
    sum_list.append(s)

for _ in range(m):
    i, j=map(int, input().split())
    if i==j:
        print(num[i-1])
    elif i==1:
        print(sum_list[j])
    else:
        print(sum_list[j]-sum_list[i-1])

"아직 실력이 부족하여 문제 해결에 있어 코드가 매끄럽지 못한 점 양해부탁드립니다..ㅎ"