[백준BOJ] 11659번 구간 합 구하기4.py

 

백준 저지에서 구간 합 구하기4를 파이썬을 통해 풀어 보았다. 

 

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

11659번: 구간 합 구하기 4

11659번 구간 합 구하기4.py

tomy9729/Algorithm

 

11659번 구간 합 구하기4

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

설명

문제 자체는 어려운 문제가 아니다. 그러나 좀 더 빨리 답을 계산하는 방법을 생각해야한다. 예를 들어 i,j가 주어졌을 때 단순히 "sum(배열[i-1:j])"로 계산하려고 하면 모든 경우에 대해서 O(n)만큼 계산 시간이 걸리기 때문에 시간 초과에 걸린다.

 

일종의 동적 계획법 문제라고 생각한다. 해당 index까지의 총 합을 저장하는 배열 sums를 선언한다. 각 index에 맞춰 해당 index까지의 총 합을 저장한다. 이때 sums의 길이를 (n+1)로 두어 sums의 가장 마지막 배열을 0으로 두는게 중요하다.

 

입력된 i,j에 대해서 sums[j-1]-sums[i-2]를 통해 O(1)만에 계산할 수 있다. 이를 통해 시간초과에 걸리지 않고 계산을 끝낼 수 있다.

코드

#11659번 구간 합 구하기4.py
import sys
input = sys.stdin.readline
if __name__ == "__main__":
  n,m = map(int,input().split())
  nums = list(map(int,input().split()))
  sums = [0]*(n+1)
  for i in range(n) :
    sums[i] = sums[i-1]+nums[i]
  for i in range(m) :
    i,j = map(int,input().split())
    print(sums[j-1]-sums[i-2])