[BOJ][Python]11659번 풀이

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

11659번: 구간 합 구하기 4

import sys
ssr = sys.stdin.readline

n,m = map(int, ssr().split())
num = [0] + list(map(int, ssr().split()))
t = [0 for _ in range(n+1)]
for i in range(1,n+1):
    t[i] = t[i-1] + num[i]
for _ in range(m):
    a,b = map(int, ssr().split())
    print(t[b]-t[a-1])

정말 알고리즘 문제는 안풀면 까먹는다는게 실감이 되는 문제였습니다. 예전에 구간합 문제를 분명 풀어봤었는데 문제를 보고 아무 생각없이 dp로 풀어야겠다 하고 입력을 인덱스로 쓰면 딱 좋겠네 싶어서 이차원 리스트로 풀었다가 메모리 초과가 나서 자세히 보니까 데이터 범위가 100000까지 되더군요. 이걸로 2차원 리스트를 만들었다간 메모리 초과가 안나는게 이상할 정도겠죠.

 

구간 합 문제는 사실 dp와 비슷하다고 해도 과언이 아닐 것 같네요. 필요할 때 마다 계산하는게 아니라 미리 계산해서 집어넣어놓는 방식을 요구하니 근본은 같다고 해도 될 것 같아요. 다만 이번 문제같은 경우 2차원 배열이나 리스트를 만드는 건 지양하는게 좋겠죠. 워낙 데이터 범위가 크니까요. 코드가 간단해서 따로 설명을 안드려도 알아보실 것 같지만 간략하게 작성해보면 처음부터 끝까지 원소를 순서대로 더해가면서 새로운 리스트를 만들고 구해야 하는 구간이 주어지면 해당 되지 않는 구간까지의 합을 빼주면 되는 문제입니다. 가령 [1,2,3,4,5]라는 숫자가 입력으로 주어졌다면 구간 합 리스트는 [1,3,6,10,15]일테니 만약 3~5까지의 구간합을 구하라고 한다면 15에서 3을 빼면 답이 나온다는 뜻이죠.