[백준 11659번 문제] 구간 합 구하기 4

이 문제는 정해진 수만큼 값을 입력받은 후에 i번째부터 j번째 수까지의 합을 구하여 출력하는 문제이다.

 

처음에 값을 입력받아서 리스트에 저장한 후에 for문으로 입력받은 인덱스에 직접 접근해서 sum이란 변수에 값을 더하여 출력하는 방법으로 구현했더니 시간초과 문제가 발생했다.

 

그래서 왜 시간 초과가 나는지 검색해보니 내가 한 방식 즉 매번 연산처리를 할 때마다 배열에 직접 접근을 하게되면 시간 복잡도가 O(NM)이 되기 때문에 1초이내에 풀 수 없다.

 

그래서 다른 방법을 고민해보다가 미리 리스트에 각 구간의 합들을 저장해 놓고 나중에 입력받은 구간마다의 합만 출력해준다면 훨씬 시간이 덜 걸릴거라는 생각이 들었다.

temp = 0
pre_sum = [0]

for i in num:
    temp += i
    pre_sum.append(temp)

임시 변수 temp에 각 구간까지의 합을 더한 후 구간의 합들을 저장할 리스트에 추가해 주는 것이다.

 

그 다음 입력받은 구간의 합만 출력해주면 끝!

for i in range(m):
    start, end = map(int, input().split())
    print(pre_sum[end] - pre_sum[start-1])

<전체코드>

import sys
input = sys.stdin.readline

n, m = map(int,input().split())

num = list(map(int, input().split()))

temp = 0
pre_sum = [0]

for i in num:
    temp += i
    pre_sum.append(temp)

for i in range(m):
    start, end = map(int, input().split())
    print(pre_sum[end] - pre_sum[start-1])