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

코드

from sys import stdin
input = stdin.readline

N, M = map(int, input().split())
lst = list(map(int, input().split()))

dp = [0]
for i in range(len(lst)):
    dp.append(lst[i]+dp[i])

for _ in range(M):
    a, b = map(int, input().split())
    print(dp[b] - dp[a-1])

설명

몇 번 틀린 문제이다.

수가 N개 주어지고 M번 만큼 그 수열의 구간합을 출력해야 하는 문제이다. 처음 봤을 때는 그냥 리스트로 수를 받고 구간합을 구할 때마다 반복문으로 더해주면 되는거 아닌가? 라는 생각이 들었다. 하지만 문제가 그리 호락호락할리가 없다고 생각했다. 그래서 dp를 이용해서 문제를 풀기로 했다.

리스트에 N개의 수를 받는다. 그리고 동적 프로그래밍을 이용해서 첫 번째 수부터 i번째 수 까지의 합을 dp[i]에 하나씩 저장한다. 마지막으로 구간을 a, b로 받고 구간 합을 구할 때 a가 포함되어야 함으로 dp[b]에서 dp[a-1]을 빼 주면 답이 된다.

 

메모리: 39468 KB

시간: 312 ms

문제

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

11659번: 구간 합 구하기 4

 

내가 틀렸던 케이스

사실 몇 번 시간 초과가 났었다. 이유는 dp 리스트에 원소를 추가하는 과정을 M번 도는 반복문에 넣었었기 때문이다.

from sys import stdin
input = stdin.readline

N, M = map(int, input().split())
lst = list(map(int, input().split()))
for _ in range(M):
    a, b = map(int, input().split())
    dp = [0]
    for i in range(b):
        dp.append(lst[i]+dp[i])
    print(dp[b] - dp[a-1])

이런식으로 썼었는데, 당연하게도 시간 초과가 났다. 이렇게 코드를 짜면 구간 합을 여러번 구하려면 같은 dp리스트를 몇 번이고 다시 만들어야 한다. 따라서 여러번 dp리스트를 참조하려면 맨 위의 코드처럼 dp는 따로 한 반복문만 돌려주게 설계해야 효율적이다. 아무래도 동적 프로그래밍에 익숙하지 않아서 이렇게 풀었던 것 같다.