[python]백준 11659번: 구간 합 구하기 4(구간합)

# 11659 구간 합 구하기 4

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

⭐ 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

num_list = list(map(int, input().split()))
sum_list = [0]
result = 0

for i in range(len(num_list)):
    result += num_list[i] 
    sum_list.append(result) 

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

📝 풀이

문제만 읽어 봤을때에는 단순 구현으로는 어렵지 않아보이는 문제였다. 주어진 조건을 그대로 코드를 옮겨서 아래와 같은 코드를 작성했었다.

import sys
input = sys.stdin.readline
N, M = map(int, input().split())

num_list = list(map(int, input().split()))
for _ in range(M):
    a, b = map(int, input().split())
    print(sum(num_list[a-1:b+1]))

위와 같은 코드를 작성해도 테스트 케이스에서 동일하게 결과 값이 나온다. 하지만 N, M의 범위가 100,000이므로 M이 커질 때 num_list의 범위를 sum을 해주다보니 시간초과가 나오는 것 같다.

🔓 정답 코드 뜯어보기

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

num_list = list(map(int, input().split()))
sum_list = [0]
result = 0

for i in range(len(num_list)):
    result += num_list[i] # 구간의 합을 result에 저장
    sum_list.append(result) # 구간의 합을 sum_list에 append

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

처음 작성했던 코드와 다른점은 합을 저장해줄 sum_list를 만들어주고, 합을 계산할 result값을 생성해줬다.  누적해서 합을 저장하므로 빼줘야 할 인덱스만 잘 조정해주면 원하는 구간 합을 구할 수 있다.

 

sum_list = [0]을 만들어서 후에 i, j값을 받을때 인덱스 값을 그대로 반영하기 위해서 초기에 0을 넣어준다.

그리고 난 후 합을 저장할 result를 생성해주고, num_list의 범위만큼 반복문을 더해준다. 구간 합을 sum_list에 계속해서 append해준다.

 

그 후 구해야되는 합 횟수 M만큼 반복문을 실행시켜주고, i, j값을 입력받아준다. sum_list의 j 인덱스 값과 sum_list의 [i-1]인덱스의 값을 빼주면 구간 합이 나오게 된다.