[알고리즘] 백준 11659 : 구간 합 구하기 4 - S3

2023.04.07 풀이

import sys
input=sys.stdin.readline

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

for i in range(1, n):
    arr[i]+=arr[i-1]

arr.insert(0, 0)

for i in range(m):
    a,b=map(int, input().split())
    print(arr[b]-arr[a-1])

• 반복문 구현이 간단해 보였는데 범위가 커서 시간초과가 날 것 같아서 누적합을 생각함
• 리스트 하나를 더 쓰는 것보단 기존 리스트에 합들을 다시 저장하는게 메모리 측면에서 더 나을 것이라고 생각함
• 구현 시 2부터 3사이의 값을 구하기 위해서는 3번째 - 2번째가 아닌 3번째-1번째 로 구해야함 -> 0~3사이의 값은 3-(범위이탈) 이므로 0번째에 0값을 넣어줌

다른 풀이

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
li = list(map(int, input().split()))
prefix_sum = [0]
sum = 0
for i in li:
  sum += i
  prefix_sum.append(sum)

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

• 새로운 배열에 저장
• 메모리는 같으나 시간이 더 빠름

for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())

    # i번째 수부터 j번째 수까지 합
    if i==1:
        print(haps[j-1])
    else:
        print(haps[j-1]-haps[i-2])

• 배열에 0을 넣지 않고 구하는 법 : 1번째(=0번째)가 문제니 그 부분만 따로 처리

check point

• 리스트에 요소 삽입 : insert(a, b) = 리스트의 a번째 위치에 b 삽입

• 누적합 추가 개념
  1
  2