[백준 파이썬] # 11549 구간 합 구하기 4

Silver III

# 11659 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

 

풀이

import sys 

N, M = map(int, sys.stdin.readline().split())
li = list(map(int, sys.stdin.readline().split()))

summary = 0
prefix_sum = [0]

for i in li:
    summary += i
    prefix_sum.append(summary)

for _ in range(M):
    i, j = map(int, sys.stdin.readline().split())
    print(prefix_sum[j] - prefix_sum[i-1])

 

오답 예시 : 시간 초과

N, M = map(int, input().split())
li = list(map(int, input().split()))
for _ in range(M):
    i, j = map(int, input().split())
    s = 0
    for k in range(i-1, j):
        s += li[k]
    print(s)

 

후기

• 배열의 특정 연속된 구간을 처리하는 경우 O(N)의 복잡도로 해결 가능하다 : 선형 복잡도를 갖는다.
  일반적인 계산 구현으로 코드를 만들면 최대 O(N^2)의 복잡도를 가질 수 있다. 선형 복잡도로 문제를 해결하기 위해 투 포인터, 구간 합을 이용할 수 있다. 이번 문제의 경우 구간 합 문제에 해당한다.
  
  
• 구간 합(Interval sum)을 빠르게 계산하기 위해 Prefix Sum을 활용한다.
  누적 합 리스트를 구하고, 구하고자 하는 구간의 값으로 부터 이전의 값을 빼줌으로써 결과값을 도출 할 수 있다.
  
  
• 코딩 테스트와 알고리즘 대회에서 자주 출제되는 유형으로 사용법을 익히는 것을 추천
  
  
• 투 포인터 문제에 대해서도 도전해보자

• 참고영상 - by 나동빈 : 매우 잘 설명되어 있으므로 꼭 참고할 것

https://www.youtube.com/watch?v=rI8NRQsAS_s