[백준] 11659_구간 합 구하기 4 (Python)

11659__구간 합 구하기 4 (Python)

0. 출처

• 유형 : 구간 합 (silver 3)
• 링크 : 11659번: 구간 합 구하기 4

1. 기록

• 22/07/01 (금)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
구하고자 하는 구간의 인덱스 숫자를 다음과 같이 바꿔준다.
0 2
1 3
4 4

[a0, a1, a2, a3, a4]
[5, 4, 3, 2, 1]

s0 = a0
s1 = a0 + a1
s2 = a0 + a1 + a2
s3 = a0 + a1 + a2 + a3
s4 = a0 + a1 + a2 + a3 + a4

[s0, s1, s2, s3, s4] 
[5, 9, 12, 14, 15]

위의 배열에서 규칙을 찾으면 쉽게 구할 수 있다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
수의 개수 / n과 합을 구해야 하는 횟수
5 3
5 4 3 2 1
1 3
2 4
5 5


- 예제 출력 1 -
12
9
1

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

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

nums = list(map(int,input().split()))

for i in range(1, len(nums)):
    nums[i] = nums[i] + nums[i-1]

for _ in range(m):
    s, e = map(int, input().split())
    s = s-1
    e = e-1
    if s == 0:
        print(nums[e])
    else:
        print(nums[e]-nums[s-1])

(4) 정리

(5) 참고