백준 2616 : 소형기관차 (Python)

본문 링크

import sys
input=sys.stdin.readline

N=int(input())
L=list(map(int,input().split()))
K=int(input()) # 소형기관차가 끌수있는 객차의 최대 개수.

dp=[ [0]*(N+1) for i in range(4)]

Prefix=[0]*(N+1)
for i in range(1,N+1):
    Prefix[i]=Prefix[i-1]+L[i-1]


for i in range(1,4):
    for j in range(N+1):
        if j>=K:
            dp[i][j]=max(dp[i][j-1] , dp[i-1][j-K]+Prefix[j]-Prefix[j-K])
        else:
            dp[i][j]=dp[i-1][j]

print(dp[3][-1])

📌 어떻게 접근할 것인가?

누적합과 다이나믹 프로그래밍을 섞은 문제였다.
누적합을 써야했다고 생각한 이유는 특정 연속수열의 합을 구할때 누적합 배열하나만 만들어놓으면 연속수열의 합을 매번 바로바로 구할수 있기 때문이다.

또한 다이나믹 프로그래밍을 써야만 했던 이유는 기관차의 최대 개수가 $50000$ 이기 때문에 $O(N^2)$ 풀이법으로는 불가능했다. 총 $2,500,000,000$번의 연산을 해야하기 때문이다.

누적합을 통해서 특정 연속수열의 합을 빠르게 구한다는건 이해했지만

$dp$ 배열을 통해 어떻게 최대값을 연속적으로 유지할지 이해하지못했다.

알고보니깐 간단하게 생각하면 점화식을 바로 세울수 있는 문제다.

• $dp[i][j]=max(dp[i][j-1] , dp[i-1][j-K] + Prefix[j]-Prefix[j-K] )$

이 점화식이 가지는 의미는 $dp[i][j]$ 값이 이전값을 그대로 가지고 갈것이냐 , 아니면 $j-K$ 인덱스(아직 소형기관차를 사용하지 않은상태) 에서 소형기관차를 쓸것이냐 ($Prefix[j]-Prefix[j-K]$)

즉 이전값을 가지고 갈래? 아니면 소형기관차를 아직 쓰지않은상태에서 소형기관차를 쓸래? 라는 의미이다.

$dp$ 문제를 많이 풀면서 처음에는 누군가의 점화식을 보는것만으로도 이해하기 많이 어려웠지만
배낭문제를 계속 풀다보니 점화식을 보기만해도 무슨 의미인지 바로 이해가 되었다.

조금만 더 연습하면 나 스스로 점화식을 완벽하게 만들수 있지 않을까 생각이 든다.
내가 생각하는 아이디어를 단 한줄의 코드로 구현하는건 어렵지만 무엇이든지 처음이 어렵지 연습하다보면 쉬워질꺼라 생각한다. 여기까지가 내가 문제를 풀면서 느낀 생각이다.

✅ 코드에서 주의해야할 부분

• 점화식은 $j>=K$ 일때 사용해준다. 인덱스 오류가 날 수 있기 때문이다.
• $j<K$일때는 그냥 이전값을 저장해준다.