[백준 11659] 구간 합 구하기 4(Feat.Python)

문제

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

 

풀이

• 위 문제를 보고 본인은 기본적인 방법을 떠올렸음,  파이썬 슬라이싱 문법을 사용하여 입력 받는 i, j 로 하나씩 더해가면 어떨까 생각하였음 => 하지만 위 방법으로 구현했을 시 문제에서 원하는 시간을 초과

# 해당코드는 시간초과가 되는 코드
import sys

input = sys.stdin.readline
N, K = map(int, input().split())
data = list(map(int, input().split()))
ans = []
count = 0
for _ in range(K):
    count = 0
    i, j = map(int, input().split())
    for k in range(i - 1, j):
        count += data[k]
    print(count)

 

• 따라서 다른 방법으로 빠르게 계산하는 방식을 떠올렸고 이를 문제에서 구간 합 알고리즘을 사용하면 빨라 질 수 있을까에 대해서 생각하고 구현해 보았음

#해당 코드는 제출 했을때 성공한 코드
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
data = list(map(int, input().split()))
li = [0]
for i in data:
    li.append(li[-1] + i)

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

  

• 입력 받은 데이터를 data 라는 리스트에 저장
• li 안에 0을 처음에 넣고 그다음 하나씩, li[1] 에는 입력받을 1까지에 대한 합, li[2] 에는 입력 받을 2까지에 대한 합이 된다. (입력이 1일 때, 배열에서는 0 으로 생각하고 문제를 해결해야 하기에 0을 하나 넣어놓았음)
• 이를 li안에 저장되어 있고 마지막 for문에서 i, j 를 입력받아 i번째 부터 j번째까지의 합을 print해준다.
• 따라서 j 번째까지의 합에서 i-1번째의 합까지의 값을 빼면, 원하는 i ~ j까지의 합이 나올 수 있다