[BOJ] 11659 구간 합 구하기 4 - python

11659번: 구간 합 구하기 4

11659번: 구간 합 구하기 4

풀이

처음에 아 뭐야 완전 쉽네? 하고 그냥 했다가 시간초과 당함 그래서 dp 테이블 써서 이전 꺼 저장하고 다시 사용하는 방법으로 했는데 이번엔 메모리 초과 그도 그런게 N이 1,000,000까지인데 최악의 경우 N*N의 크기일 수 있으니 메모리 초과는 당연.. index 0부터 n까지의 누적합을 저장해두고 빼는 것으로 하자!

메모리 초과 dp코드

import sys
sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip()

N,M = map(int,input().split(" ")) #각 1,000,000개씩
num = list(map(int,input().split(" ")))
mul = [tuple(list(map(int,input().split(" ")))) for _ in range(M)]

#dp = [[0] * (N+1) for _ in range(N+1)]
dp = [{} for _ in range(N)] #[{},{},{},{}...{}] N개

def dfs(a,b):
    if a == b:
        return num[b]
    if b in dp[a]:
        return dp[a][b]
    else: #(1,5) (1,4) + num[5]
        dp[a][b] = dfs(a,b-1) + num[b]
    return dp[a][b]

for m in mul:
    print(dfs(m[0]-1,m[1]-1))

코드

import sys

def input():
    return sys.stdin.readline().rstrip()

N,M = map(int,input().split(" ")) #각 1,000,000개씩
num = list(map(int,input().split(" ")))
mul = [tuple(list(map(int,input().split(" ")))) for _ in range(M)]

#0부터 누적합 구하기
accum_sum = [num[0]] * N
for i in range(1,N):
    accum_sum[i] = accum_sum[i-1] + num[i]

for m in mul:
    a,b = m[0]-1,m[1]-1
    if a == b:
        print(num[a])
    elif a == 0:
        print(accum_sum[b])
    else:
        sum = accum_sum[b] - accum_sum[a-1]
        print(sum)

얻어가는 것

• 누적합

#0부터 누적합 구하기
accum_sum = [num[0]] * N
for i in range(1,N):
    accum_sum[i] = accum_sum[i-1] + num[i]

느낀점

"211110"

소요 시간 : 1h

• 시간초과 + 반복해서 사용하는거 보고 dp사용해보려 했는데
• 메모리 초과도 생각을 해야 한다는 것을 깨달았다.
• 누적합도 좋은 방법인듯!!! 머리속에 잘 넣어두자!!