[Python] 백준 2616번 - 소형기관차

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

2616번: 소형기관차

 

 

문제 알고리즘 분류에 '누적합'이라고 나와있는데 누적합으로 안 푼 바보가 여기 있다..

최대로 끌 수 있는 객차 수를 하나하나 계산해서 단순합으로 넣으려고 하니까 코드도 복잡해지고 안 풀린 거였다.

2021.07.10 - [HUFS/HUFS 모각코 캠프] - [모각코] 210710 Today I Learned (단순합으로 시도한 코드)

단순합으로 하면 예제는 풀리긴 하는데 최대로 끌 수 있는 객차 수가 몇이냐에 따라 계산을 다시 해줘야 해서 코드가 돌아가지 않았다.

 

단순합 대신 누적합으로 하면 풀린다.

누적합을 dp[0]으로 넣을지, 개별적으로 리스트를 하나 만들어서 넣을지는 취향 차이 같은데 나는 둘 다 했다.

인덱스 헷갈릴까봐 개별리스트로 먼저 만들어서 성공한 후에 dp[0]에 넣은 버전으로 다시 고쳤다.

 

 

 

(설명은 나중에 이해하기 쉽게 누적합 리스트 accu로 하겠음)

 

• 현재 칸을 포함하지 않는 경우의 최댓값 (dp[i][j-1])
• 현재 칸을 포함한 경우(accu[j] - accu[j-m]) + 현재 칸 전에 끌 수 있는 최댓값(dp[i-1][j-m])

 

이 둘의 최댓값을 dp[i][j]에 넣는다.

 

i = 0인 경우, 끌 수 있는 최대 객차의 수가 1이므로 현재 칸 전에 끌 수 있는 최댓값은 없다. => 조건 나눠줘야 함.

 

 

 

#누적합 리스트 accu 사용

import sys
n = int(sys.stdin.readline()) #기관차가 끌고 가던 객차의 수
people = [0] + list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline()) #소형기관차가 최대로 끌 수 있는 객차의 수
dp = [[0 for j in range(n+1)] for i in range(3)] #4 = 단순합 1칸 + 소형기관차 3대
accu = [0 for j in range(n+1)] #누적합

for j in range(1, n+1):
    accu[j] = accu[j-1] + people[j]

for i in range(3):
    for j in range((i+1)*m, n+1):
        if i == 0:
            dp[i][j] = max(dp[i][j-1], accu[j]-accu[j-m])
        else:
            dp[i][j] = max(dp[i][j-1], (dp[i-1][j-m] + accu[j] - accu[j-m]))
print(dp[-1][-1])

 

 

#dp[0]에 누적합 저장

import sys
n = int(sys.stdin.readline()) #기관차가 끌고 가던 객차의 수
people = [0] + list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline()) #소형기관차가 최대로 끌 수 있는 객차의 수
dp = [[0 for j in range(n+1)] for i in range(4)] #4 = 누적합 1칸 + 소형기관차 3대

for i in range(4):
    for j in range(1, n+1):
        if i == 0: #누적합
            dp[i][j] = dp[i][j-1] + people[j]
        elif j < i*m:
            continue
        elif i == 1 and j >= i*m:
            dp[i][j] = max(dp[i][j-1], dp[0][j]-dp[0][j-m])
        else:
            dp[i][j] = max(dp[i][j-1], (dp[i-1][j-m] + dp[0][j] - dp[0][j-m]))
print(dp[-1][-1])