알고리즘/백준[baekjoon]

[baekjoon] 백준 11659번 : 구간 합 구하기 4 (by python 파이썬) 구간합

코딩하는이씨 2022. 7. 23. 15:51
728x90
반응형

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

 

11659번: 구간 합 구하기 4

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j

www.acmicpc.net

 

정답 code

#구간 합 구하기
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
num = list(map(int,input().split()))

sum_list = [0]
total = 0
for i in range(len(num)):
    total += num[i]
    sum_list.append(total)

for i in range(m):
    x,y = map(int,input().split())
    print(sum_list[y] - sum_list[x-1])

 

solution

처음엔 단순히 입력된 구간끼리 더하고 출력하는 코드를 만들었는데 시간초과가 발생했다.

이중 for문이 되면서 시간복잡도가 늘어나며 시간초과가 된것 같다.

 

누적합 알고리즘을 통해 시간초과를 해결하였다.

먼저 sum_list에 누적합을 넣어주는데 인덱스 초과를 방지하기위해 0을 넣어준다.

 

위의 단계를 수행하게 되면

sum_list = [0, 5, 9, 12, 14, 15]

와 같은 상태가 된다.

 

그다음은 m만큼 x, y의 입력을 받고 합을 구해주면되는데

예제 처럼 1,3을 구하고 싶으면 3번 인덱스의 값 (12)에서 1-1을 한 인덱스의 값(0)을 빼주면 된다.

 

728x90
반응형