[백준] 11659번 구간 합 구하기 4 - python

 

<문제>

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

11659번: 구간 합 구하기 4

<시간 복잡도>

우선 이문제는 일반적인 for 문을 이용해서 풀으면 시간 초과의 문제가 나오게 된다.

아마 n^2의 시간 복잡도 때문이라고 생각한다. python이 1초에 몇 만번인지는 기억이 안나지만 그만큼 연산을 하기 때문에

 

<코드>

import sys

n, m = map(int, sys.stdin.readline().split())
num_list = [0]+list(map(int,sys.stdin.readline().split()))
dp = [0]* 100001
for i in range(1,len(num_list)):
    dp[i] = num_list[i] + dp[i-1]


for _ in range(m):
    x,y = map(int,sys.stdin.readline().split())

    print(dp[y]-dp[x-1])

<해설>

 

아무튼 이문제를 풀기 위해서는 dp 를 이용해야 한다. 그중 메모지 에이션을 이용해서 풀어야 풀 수 있다.

 

dp 로 누적 합을 저장한다. 예를 들어

1,2,3,4 의 배열이 들어온다면

dp에 dp =[ 1, 1+2, 1+2+3, 1+2+3+4]를 저장해주면 된다.

끝

 

참고로 이문제는 

https://zoozoozoo.tistory.com/566

[백준] 11660번 구간 합 구하기 5 - python

이 문제를 푸는데 도움이 된다.