[모각코] 210710 Today I Learned

<백준 2616번 - 소형기관차>

짜증나서 돌아버릴 것 같다. DP는 익숙하지 않아서 어렵다.. 

테이블에 들어갈 요소 생각하고 점화식만 잘 세우면 되는데 그 두 개가 왜 이리 어려울까..

다 풀고 나서 제출 돌려보니 런타임 에러가 났는데 최대로 끌 수 있는 객차의 수가 달라질 때를 고려하지 않아서 그런 것 같다.

단순합(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: #단순합
            if j == 1:
                dp[i][j] = 0
                continue
            dp[i][j] = people[j-1] + people[j]
        else:
            if j < (i*2):
                dp[i][j] = 0
            elif i == 1:
                dp[i][j] = max(dp[i][j-1], dp[0][j])
            else:
                dp[i][j] = max(dp[i][j-1], (dp[0][j]+max(dp[i-1][:j-m+1])))
print(dp[-1][-1])

 

 

 

 

#시간초과 코드 (단순합을 개별 리스트로)

단순합 부분을 아예 다른 리스트로 만들어서 최대로 끌 수 있는 객차 부분 해결해줬는데, 그랬더니 시간 초과 뜬다.......

오늘은 여기까지.. 다음 기회에...

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대
simple = [0 for j in range(n+1)] #단순합

for j in range(1, n+1):
    if j < m:
        simple[j] = 0
        continue
    for i in range(j, j-m, -1):
        simple[j] += people[i]

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

 

---

success !

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