안녕하세요.
이번 포스팅은 백준 온라인 저지의 11659번 문제 풀이입니다.
문제 이름은 "구간 합 구하기 4" 입니다.
문제
문제 링크는 바로 밑의 링크를 확인해주세요.
https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
|
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
num = list(map(int, input().split()))
psum = [0]
temp = 0
for i in num:
temp = temp + i
psum.append(temp)
for i in range(M):
s, e = map(int, input().split())
print(psum[e] - psum[s-1])
|
cs |
핵심: 해당 문제는 시간 제한이 0.5초이므로 구간 합을 이용한 문제로 풀어야 시간 제한 안에 계산이 됩니다.
리스트 A가 [5, 4, 3, 2, 1] 일 때 1부터 3까지의(인덱스0부터 인덱스2까지) 합은 5 + 4 + 3으로 계산하는 것 보다
합 배열을 psum을 선언하여 [0, 5, 9, 12, 14, 15] 에서 인덱스3 - 인덱스0을 하는 것이 시간 복잡도를 줄일 수 있습니다.
1~2. sys 라이브러리를 불러와서 속도를 향상시킵니다.
3. 줄의 개수 N과 합을 구해야 하는 횟수 N을 입력받습니다.
4. N개의 수를 입력 받습니다.
5~6. 합 배열을 선언하고 합 배열을 저장하기 위한 temp를 선언합니다.
7. 입력 받은 리스트를 for문을 통해서 순차적으로 이동합니다.
8~9. temp를 사용하여 이전의 합 + 현재의 수를 합 배열에 저장합니다.
10. 합을 구해야 하는 횟수 M만큼 반복합니다.
11~12. 합 배열을 이용한 계산으로 결과값을 출력합니다.
댓글