백준 2616 소형기관차 - 파이썬
접근 열 길이가 기차의 수 + 1이고, 행 길이가 3인 dp 행렬로 접근한다. 13번째 행은 각각 현재 인덱스에서 13번째 열차가 골라졌다면 실을 수 있는 최대 손님의 수다. 입력으로 받은 train 리스트를 탐색하며 window 만큼 떨어져 있는 dp 를 업데이트 한다. dp 업데이트는 dp[현재 열 - window][현재행 - 1] 과 dp[현재 열 - 1][현재 행] 중 큰 것을 고른다. 사고 반복되는 연산을 최소화하는 DP 문제를 연습하는 중이니 다른 최적화도 가능하다면 시도해보자. 문제에서 소형 기관차의 길이가 길다면 겹치는 구간을 반복해서 구해야 할 것이다. ...