[Python] 11441번: 합 구하기 풀이

---

백준 풀이

13783번: 합 구하기 풀이

---

 

 

 

문제 Link : https://www.acmicpc.net/problem/11441

11441번: 합 구하기

 

 

 

 

단순한 합 구하기 문제인 것 같다.

그러나 특히 python같은 느린 언어로 정직하게 짤 경우, 시간초과가 발생하게 된다.

 

import sys
input = sys.stdin.readline

N = int(input())

n_list = list(map(int, input().split()))
M = int(input())
for i in range(M):
    a, b = map(int, input().split())
    nsum = 0
    for i in range(a-1, b):
        nsum += n_list[i]
    print(nsum)

 

그래서 사용해야하는게 누적합인데, 기본적인 내용은 구글을 찾아보도록 하자. (말그대로 누적된 합)

미리 누적합 배열을 만들어놓는다면, 이를 활용해 구간합도 구할 수 있다.

이런 늑김

 

그래서 다시 코드를 작성했고, 이를 실행시켰다

import sys
input = sys.stdin.readline

N = int(input())

n_list = list(map(int, input().split()))
presum = [n_list[0]]
for i in range(1, N):
    presum.append(presum[-1] + n_list[i])


M = int(input())
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        print(presum[b-1])
    else:
        print(presum[b-1]-presum[a-2])

 

누적합을 이용하면 시간복잡도를 줄일 수 있다.

 

github link(code) : https://github.com/dubini0/progamming_stuff/blob/main/baekjoon/%5B2%5D%20%2010000-14999/11441_%ED%95%A9%EA%B5%AC%ED%95%98%EA%B8%B0.py

GitHub - dubini0/progamming_stuff: programming examples