[백준 11659번-구간합 구하기 4]-파이썬

solved.ac 난이도 :  silver3

백준 11659번- 파이썬 풀이

 

<문제>

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

11659번: 구간 합 구하기 4

<풀이>-누적합

배열의 각 위치별 누적합을 구한다.

 

b까지의 누적합을 구한후 (a-1)까지의 누적합을 빼면 a부터 b까지의 누적합을 구할 수 있다.

 

예를들어 다음과 같은 배열을 살펴보자

 

다음 배열에서 2~4구간의 합을 구해보자

인덱스	0	1	2	3	4	5
원소	1	2	3	4	5	6
누적합	1	3	6	10	15	21

 

0~4까지의 누적합 : 15

 

0~1까지의 누적합 : 3

 

따라서 2~4까지의 누적합은 0~4까지의 누적합에서 0~1까지의 누적합을 뺀 12가 된다.

728x90

<코드>-파이썬

import sys

n,m = map(int,sys.stdin.readline().split())
num = list(map(int,sys.stdin.readline().split()))
temp = [0]
sum_a = 0
for i in num:
    sum_a+=i
    temp.append(sum_a)
for _ in range(m):
    a,b = map(int,sys.stdin.readline().split())
    print(temp[b]-temp[a-1])

-마치며-

필자는 처음 이문제를 풀때 굉장히 단순히 생각했다.

처음 풀이는 파이썬의 sum 함수를 활용해서 배열을 a부터 b까지 단순히 슬라이싱해 합을 구했다.

(sum(array[a-1:b])

풀고나니 이 문제가 왜 난이도가 silver3나 되는지 의아했다.

하지만 역시나 이렇게 풀면 시간초과가 발생했다.

문제를 때론 단순히 푸는게 도움이 되지만 이런경우는 너무 단순하면 좀더 생각을 더해봐야 할거 같다.