구간 합 - (1)

이론

구간 합 이용 시 합 배열을 먼저 구해야 한다.

s[i]=A[0]+A[1]+...+A[i]

합 배열을 미리 구해놓으면 시간 복잡도 O(n)=>O(1) 로 줄어든다.
ex) A[i]~A[j] 까지 구간 합 구하려면 for문을 돌아야 하기 때문에 시간 복잡도 O(n)

합 배열 만드는 공식

S[i]=S[i-1]+A[i]

구간 합 구하는 공식 (i~j 까지)

S[j]-S[i-1]

구간 합 구하기 - 1 (백준 11659번, 시간 제한: 0.5초)

문제: 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

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

출력: 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

입력 예시
5 3
5 4 3 2 1
1 3
2 4
5 5

출력 예시
12
9
1

코드 예시

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
listNum=list(map(int,input().split()))
accumSum=[0]
temp=0
for i in listNum:
    temp+=i
    accumSum.append(temp)
for i in range(M):
    a,b=map(int, input().split())
    print(accumSum[b]-accumSum[a-1])

결국 제한 시간 안에 해당 문제를 풀기 위해서는 부분 합을 사용해야 한다. 이는 input 에서 받아올 때 같이 부분 합 배열을 만들어 주면 된다.

실제 부분 합 계산을 할 때는 O(1) 만큼의 시간만 필요하다.

여기서 새로 추가된 부분은 sys 를 import 하는 것이다.
sys.stdin.readline() 은 시스템의 표준 입력 스트림을 나타내는 객체이다.
한 줄을 입력 받고 읽은 값을 문자열로 반환한다.
이때 \n 까지 포함해서 반환 하기 때문에, .rstrip() 메서드를 추가하는것이 일반적이다.

상대적으로 input() 함수에 비해 빠르다. input() 함수는 사용자가 입력 후 enter를 누르기 전까지 프로그램이 입력 대기 상태로 머무르게 되는 특징이 있다.