2616 소형기관차

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

#dp

2616번: 소형기관차

#2616

'''

오랜만에 왔다

코드부터 시작하면

'''

train=int(input())
#기차 입력

guest=list(map(int,input().split()))
#손님 순서

min_train=int(input())
#소형기관차 수용량

"""
생각해보자
조건 1. 소형기관차 숫자
2. 기관차 번호
"""

dp=[[-1 for i in range(train)] for j in range(3)]
#dp 생성 (이것만 해도 끝났다고 보면 된다)

def f(number,train_number):
    #함수 생성

    if train_number+min_train*(3-number)>train:
#만약 지금 보는 번호에서 최대 수용량을 (번호에 따라 다르게 곱해진)수를 더했을때 기차 최대 수용량을 넘으면 허수로 #본다

        return 0
    
    if number==3:
#소형 기관차 끝났어용

        return 0
    
    if dp[number][train_number]!=-1:

        return dp[number][train_number]
#탐색을 해서 앞으로의 계산이 끝났을경우에는 그냥 전에 했던거 하셈

    dp[number]train_number]=f(number+1,train_number+min_train)+sum(guest[train_number:train_number+min_train])
#뒤에서부터 계산하는 점화식 이거 그냥 내 머리에서 안나온다 어렵네

    if train_number+1<train:         
        dp[number][train_number]=max(dp[number][train_number],f(number,train_number+1))
#1을 더하는것도 경우의 수중 하나 비교해준다.

    return dp[number][train_number]
#최적화 답
"""
1. 1씩 넘기거나
2. 리미트 만큼 넘기거나.
"""

print(f(0,0))

#나쁘지 않지만 이를 계산해보면 놀랍게도 믿기싫은 시간이 보여지게 된다. 최적화 실패했다는 뜻, 다른 코드를 확인하게 되었다.

 

#이는 모두 테스트케이스의 오류인걸로 확인됨 내가 확인함 ;;

 

#다른 코드 2616 소형 기관차 정리

n=int(input())
#n 입력

people=list(map(int,input().split()))
#사람 순서

m=int(input())
#m 입력

cumsum=[0]
#또하나의 dp라고 볼 수 있음

value=0
#0부터 시작하여 하나씩 더해갈꺼임

for p in people:
    value+=p
    cumsum.append(value)
#0부터 시작하여 현재 보는 p까지의 합이 담겨져있는 cumsum 생성

dp=[[0]*(n+1) for _ in range(4)]
#dp 생성 y축은 소형 기관차 번호 x축은 총 기차 좌석

for i in range(1,4):
#n+1해줬기때문에 번호대로 갈 수 있음

    for j in range(i*m,n-((3-i)*m)+1):
#여기서 좀 변화를 줬는데 뒤에서부터 소형기관차 를 다 못넣는 경우는 다 스킵하게 했음

        if i==1:
            dp[i][j]=max(dp[i][j-1],cumsum[j]-cumsum[j-m])
#i==1인 경우에는 이전의 값이 없기 때문에 i-1역시 없다 차별화를 줌

        else:

            dp[i][j]=max(dp[i][j-1],dp[i-1][j-m]+cumsum[j]-cumsum[j-m])
#이전까지의 최대값과 전 번호의 것+ 현재 보는 값 - 기관차 전 합 해서 사이 값만 계산 한거를 집어 넣음

print(dp[3][n])

#끝까지보고 최대값 입력

 

#솔직히 다시 오면 까먹을 것 같다. 일단 생각해야되는것은 기본적으로 조건을 생각해봐야한다는 것이다. 위와 밑의 가장 큰 차이점은 또다른 dp를 넣었다는 것 또다른 dp를 넣음으로써 불필요한 계산을 최소화 하였다는 것이 시간에 영향을 준 요소인 것 같다.