Algorithm/알고리즘 문제
[BOJ/Python] 11659번 구간 합 구하기 4
은 딩
2023. 1. 9. 00:14
https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
누적합으로 풀어야 시간 초과가 안난다.
맞은 코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
list_a = list(map(int, input().split()))
sum = []
sum.append(list_a[0])
for i in range(1, n):
sum.append(sum[i-1]+list_a[i])
for i in range(m):
x, y = map(int, input().split())
if x== y:
print(list_a[x-1])
elif x == 1:
print(sum[y-1])
else:
print(sum[y-1]-sum[x-2])더 깔끔한 코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
list_a = [0] + list(map(int, input().split()))
sum = []
temp = 0
for i in range(n+1):
temp += list_a[i]
sum.append(temp)
for _ in range(m):
i, j = map(int, input().split())
print(sum[j] - sum[i-1])