[알고리즘][Python] 백준(BOJ) 11659 구간 합 구하기 4_파이썬

 

11659 구간 합 구하기 4    https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

 

 

 

문제 풀기 전 공부할 것 : 누적 합

 

 

 

 

 

 

 

풀이 1

<내용>

• 완전 탐색으로 해결하면 시간 초과가 발생할 수 있기 때문에 누적 합을 이용해서 해결하기
• 누적 합 리스트 nums_add를 구하면 i에서 j까지의 합은 nums_add[j] - nums_add[i-1]과 같다.
  • nums_add[j]는 j까지의 숫자의 합이다.
  • nums_add[i-1]는 i-1까지의 숫자의 합이다.

 

 

 

<코드>

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums_add = [0]
for i in range(n):
    nums_add.append(nums_add[-1]+nums[i])
for _ in range(m):
    i, j = map(int, input().split())
    if i == 1:
        print(nums_add[j])
    else:
        print(nums_add[j]-nums_add[i-1])