BAEKJOON_11659 "구간 합 구하기 4" PYTHON

[백준] 11659번 Python 파이썬

 

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

11659번: 구간 합 구하기 4

이번 문제에서는 누적합 알고리즘을 사용하였다.

 

num 리스트의 누적합을 num_s 리스트에 담아주었다. 

 

리스트 num_s의 첫 번째 원소는 num리스트의 첫 번째 요소를 그대로 담아주고  2번째 원소부터는 for문을 사용하여 전 인덱스의 원소에 해당 인덱스 원소에 더한 값을 넣어주었다. 

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

# 'section'이라는 배열을 만들어 출력할 합의 범위를 담아준다.
section = []

for i in range(m):
    st = list(map(int, input().split()))
    section.append(st)

# 누적합 값을 담기 위한 'num_s' 배열을 생성한다. 
num_s = [int(num[0])] # 첫 번째 원소는 num 배열의 첫 번째 원소값을 넣어준다.

for i in range(1, n):
    num_s.append(num_s[i-1] + num[i]) # 누적된 값을 차례로 넣어준다.

# for문을 사용하여 출력하는데 1번째 원소부터 더할 때와 그 외의 경우를 나누어 출력해야한다.
for i in section:
    if i[0] != 1:
        print(num_s[i[1]-1] - num_s[i[0]-2])
    else:
        print(num_s[i[1]-1])

첫 번째 원소부터 합을 구하는 부분에서 시간이 오래 걸렸다.

혼자 공부하며 올리는 블로그입니다. 틀린 내용은 댓글 남겨주시면 감사하겠습니다.