[BOJ/python] 11659: 구간 합 구하기 4

문제

✔️ silver 3
누적 합

문제 흐름

처음에는 그냥 sum을 이용해서 풀면 안되나? 했다.
물론 M이 100,000이나 되니 메모이제이션을 하지 않으면 안되겠구나 하는 생각을 해서 아래와 같이 썼었다.
memo[x] = sum(n_num[:j]) - sum(n_num[:i-1])
지금 보니 웃기지만 매번 저 sum을 계산하는데 O(N)의 시간이 소요되기 때문에 딱봐도 비효율적이다. 게다가 메모이제이션을 하는 의미도 딱히 없음..
그리고 당연스럽게도 결과는 시간초과였다. ㅎㅎ..

memo를 제대로 활용하기 위해서는 아래와 같은 방식으로 memo를 계산해야겠다 생각했다.
memo[x] = memo[x - 1] + n_num[x]
그리고 어디까지 memo가 계산됐는지 확인하기 위해 cur를 만들었다.

1. 함수 dp에서 조건에 맞춰 a, b를 진행한다.
   a) cur >= j라면 바로 cur값을 반환하고,
   b) cur < j라면 j까지 반복해서 memo[x]를 계산해 memo를 채워준 뒤 cur값을 반환한다.
2. 함수를 빠져나와 memo[j] - memo[i - 1]을 계산해 출력한다.

코드

# 구간 합 구하기 4
# dp

import sys
input = sys.stdin.readline

def dp (i: int, j: int, cur: int, n_num: list, memo: list):
    if cur >= j:
        return cur

    for x in range(cur + 1, j + 1):
        memo[x] = memo[x - 1] + n_num[x]
        cur += 1
    
    return cur

if __name__ == "__main__":
    n, m = map(int, input().split())
    n_num = list(map(int, input().split()))
    n_num.insert(0, 0)
    memo = [0 for i in range(n + 1)]
    cur = 0

    for k in range(m):
        i, j = map(int, input().split())
        
        cur = dp(i, j, cur, n_num, memo)
        result = memo[j] - memo[i - 1]
        print(result)

마무리

방향이 딱 보이는 문제라 어려운 문제는 아니었지만 그래도 간만에 힌트나 gpt의 도움 없이 dp문제를 풀었다!
뿌듯~!
그리고 새삼 python의 내장 함수·메소드에서 성능을 기대하지 말아야겠다는 생각을 했다. ㅎ..