[11659] 백준 구간 합 구하기 1 python

	백준 문제풀이		python
			No. 11659 구간 합 구하기 1

 

 

#파이썬 #백준 #문제풀이 #11659 구간 합 구하기 1

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

11659번: 구간 합 구하기 4

 

이번 글에서는 누적합, 구간 합을 구하는데 중점을 둔다. S[i] = S[i-1] + A[i]

 

N M

N개의 수

i ~ j 까지 합을 구하는 문제이다. 최대 부분 배열이 생각난다.

 

 

예제 입력:

5 3
5 4 3 2 1
1 3
2 4
5 5

 

예제 출력

12
9
1

---

// 알고리즘

가장 중요한 목적이 무엇인지?

for 문을 적절하게 수를 나눠야할거같다.

 

왜 이런 방법을 선택했는지?

파이썬은 슬라이싱이 편하므로. 슬라이싱과 sum함수를 이용해 볼 수 있지 않을까?

---

// 계획하기

	함수명	설명
1.
2.
3.

 

---

// 구현하기

-> How?

어떻게 구현?

 

 

->Why?

왜 이런 방법을?

---

// 수정하기

 

중간에 버퍼가 차서 멈추는 경우가 발생했다.

따라서 input()에 버퍼가 걸리는 거 같아서

list(map(int,sys.stdin.readline().split()))

readline함수로 변경하였다.

 

그래도 발생하길래 디버깅 과정에서 살펴봤다.

 

import sys
def main():
    N, M = map(int,input().split())
    lists = []
    lists = list(map(int,sys.stdin.readline().split()))

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

main()

def main():
    # 첫 줄을 읽어와서 처리합니다.
    lists = []
    N, M = map(int, input().split())
    lists = list(map(int, input().split()))

    # 두 번째 줄부터 마지막 줄까지 한 번에 읽어와서 처리합니다.
    inputs = sys.stdin.read().splitlines()
    for line in inputs:
        i, j = map(int, line.split())
        print(sum(lists[i-1:j]))

main()

 

둘 다 버퍼에 계속 걸려서 가장 간단하게 입력받을 때는 행동하지 않기로 했다.

 

자세한 오류는 뒤에 찾아볼 예정이다.

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
lists = list(map(int,input().split()))
ItoJ = []
for k in range(M):
    ItoJ += list(map(int, input().split()))

for k in range(M):
    print(sum(lists[ItoJ[k*2]-1:ItoJ[k*2+1]]))

그렇지만 이렇게 구현하면 찾아야하는 개수만큼 계속 for문을 돌아야해서 시간이 낭비된다. 차라리 누적합을 미리 계산하는 것도 나쁘지 않다. for문을 1번돌때 모든 누적합을 미리 계산하는 것이다. 구간 합을 구하기 위해서는 합 배열을 구해야한다. 합 배열을 만드는 공식은 S[i] = S[i-1] + A[i]

 

합 배열만 미리 구해두면 구간 합은 한 번의 계산으로 구할 수 있다.

---

// 완성코드

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
numbers = list(map(int, input().split()))
prefix_sum = [0]
temp = 0

for i in numbers:
    temp = temp+i
    prefix_sum.append(temp)

for i in range(M):
    s, e = map(int,input().split())
    print(prefix_sum[e] - prefix_sum[s-1])