[백준] 11659 구간 합 구하기 4

www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
n_list = list(map(int, input().split()))
m_list = []
for _ in range(m):
    m_list.append(tuple(map(int, input().split())))

for m_tmp in m_list:
    print(sum(n_list[m_tmp[0]-1:m_tmp[1]]))

수업때 했던것처럼 구간에 대한 합들을 구했는데 시간 초과가 걸렸다.

문제의 범위가 m,n이 둘다 100,000 개인 경우에서 모든 구간을 더하는(sum(1~100,000)) 시간이 얼마나 걸릴지 궁금해져서 만들어보니 54초 걸렸다.

동적계획법을 사용해야한다는 생각은 들었지만 막상 어떻게 구현해야할지 막막했다.

그래서 타인의 코드를 확인하였다.

방법은 인덱스를 처음부터 끝까지 먼저 구해놓고 각각의 범위에 대해서 빼는 방식으로 구현한다.

예를 들어 n=10이고 5에서 8까지 범위의 구간합을 구한다고 하자.

첫번째로 n에서 구간이 1인 부분(1~1)의 합부터 구간이 10인 부분(1~10)의 합까지 구해놓는다.(메모이제이션)

그 다음 1부터 8까지의 구간합과 1부터 4까지의 구간합을 모두 알고있으므로 서로 빼주면 5부터 8까지의 구간합을 구할수 있다.

import sys
input = sys.stdin.readline

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

dp_list = [0]*(n+1) #index 쉽게 접근
for i in range(1,n+1):
    dp_list[i] = dp_list[i-1] + n_list[i-1]

for _ in range(m):
    s, e = map(int, input().split())
    print(dp_list[e]-dp_list[s-1])

 

같은 방법으로 m,n이 둘다 100,000 개인 경우에서 모든 구간을 더하는(sum(1~100,000)) 시간을 구했을때 0.31초가 걸렸다.