[백준][DP] 2616.소형기관차

2616.소형기관차

 

 

• 풀이
  • 2차원 DP
  • dp[i][j] : i개의 소형기관차를 사용하는 동안 j 번째 칸까지의 최대 손님 수
  • 최대 끌수 있는 객차 수 k만큼 한번에 데려가기 때문에 현재 칸을 넣을건지 안넣을건지
    • 현재 칸 안넣는다 ⇒ dp[i][j-1]
    • 현재 칸 넣는다 → 하나 적게 j-k번까지 끌고+ 현재칸 ⇒ dp[i-1][j-k]+(trains[j]-trains[j-k]

n=int(input())
trains=[0]+list(map(int,input().split()))
k=int(input())
for i in range(1,n+1):
    trains[i]+=trains[i-1]
dp=[[0 for _ in range(n+1)] for _ in range(4)]

for i in range(1,4):
    for j in range(k,n+1):
        dp[i][j]=max(dp[i][j-1],dp[i-1][j-k]+(trains[j]-trains[j-k]))

print(dp[3][n])