백준 11659 파이썬, 구간 합 구하기 4, python

문제풀이

처음 이 문제를 보았을 때는,  두번째에 주어진 숫자들을(5 4 3 2 1) 리스트로 생성하고, M개의 줄에 입력 받을 숫자들

(1, 3), (2, 4), (5, 5) 를 인덱싱으로 접근해서 풀이하였지만 시간초과

# 구간 합 구하기 4
n,m = map(int,input().split())
n_list = list(map(int,input().split()))
# [5, 4, 3, 2, 1]
for _ in range(m):
    first, end = map(int,input().split())
    first -= 1
    add = 0

    for i in range(first, end):
        add += n_list[i]
    
    print(add)

그 이유는 N개의 원소로 이루어진 배열이 주어졌을 때, 반복문을 통해 부분 배열의 합을 구하려면 시간복잡도 O(N)이 걸리는데 이 때문에, 예제는 맞았지만 시간초과가 생기는 것 같다.

 

방법을 생각해보다 이런 종류의 문제의 접근은 부분합을 이용하면 된다고 한다. 부분합은 시간복잡도 O(1)이기 때문에 반복문을 통해 배열의 합을 구하는 것보다 훨씬 빨리 정답을 찾을 수 있다.

우리가 풀이하는 문제는 1차원 배열이기 때문에 다음과 같이 풀이 했다.

import sys
# 구간 합 구하기 4
n,m = map(int,sys.stdin.readline().split())

n_arr = list(map(int,sys.stdin.readline().split()))
# [5, 4, 3, 2, 1]


# 부분합을 구할 리스트를 만들어 주기
sum_arr = [0 for _ in range(n+1)]
for i in range(1, n+1):
    sum_arr[i] = sum_arr[i-1] + n_arr[i-1]
# [0, 5, 9, 12, 14, 15]


for _ in range(m):
    first, end = map(int, sys.stdin.readline().split())
    print(sum_arr[end]-sum_arr[first-1])

 

2차원도 이처럼 부분합으로 접근해서 풀이할 수 있다! 참고는

https://yiyj1030.tistory.com/489 님의 블로그에서 하였다!