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

문제

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

풀이

[백준] 11659번 : 구간 합 구하기4 🥈(실버 3)
🎯 39.479%
⏰ 걸린 시간 : 20분
⏲ 시간복잡도
구간 합 O(n)

• 알고리즘 유형 : [구간 합]

📚 [구간 합]

✅ 풀이방법 & 구간 합 알고리즘로 푼 이유?
0. 구간 합을 먼저 구해놓는게 관건이다.
1. N^2으로 구해버리면 시간초과가 발생하기 때문이다.

코드(code)

import sys
input=sys.stdin.readline
N, M = map(int, input().split())
nums = list(map(int,input().split()))
prefix_sum = []

psum=0
for i in nums:
    psum += i
    prefix_sum.append(psum)


for i in range(M):
    start, end = map(int,input().split())
    if start != 1:
        print(prefix_sum[end-1]-prefix_sum[start-2])
    else: 
        print(prefix_sum[end-1])

회고

구간 합 처음 푼건데 풀면서 늘 것 같다.

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/Prefix_Sum/11659(%EA%B5%AC%EA%B0%84%20%ED%95%A9%20%EA%B5%AC%ED%95%98%EA%B8%B04).py