[Python] 백준 2240. 자두나무 (DP)

문제 링크

문제 풀이 (bottom-up DP)

• dp[시간][이동횟수] = (시간)까지 (이동횟수)만큼 이동했을 때 얻을 수 있는 최대 자두 개수 로 설정.
• 그래서 1초일 때,
  • 0번 이동했으면 1번 나무 아래이기 때문에 dp[1][0] = jadu[1] % 2,
  • 1번 이동했으면 2번 나무 아래이기 때문에 dp[1][1] = jadu[1] // 2.
• 시간 t일 때까지 w 번 이동했다고 했을 때 얻을 수 있는 최대 자두 개수 dp[t][w는
  (전 시간 t-1까지 w 번 이하로 이동했을 때 얻었던 최대 자두 개수) + (t일 때까지 총 w 번 이동한 위치에서 얻는 자두 개수)이다.
  • (전 시간 t-1까지 w 번 이하로 이동했을 때 얻었던 최대 자두 개수) = max(dp[time - 1][0:w + 1])
  • (t일 때까지 총 w 번 이동한 위치에서 얻는 자두 개수)인 j는
    • 이동 횟수 w가 홀수이면 무조건 2번 나무 아래, 짝수면 1번 나무 아래에 있기 때문에
    • w가 짝수이면 j = jadu[time] % 2, 홀수이면 j = jadu[time] // 2

코드

import sys

input = sys.stdin.readline

if __name__ == '__main__':
    T, W = map(int, input().split())
    jadu = [0] + [int(input()) for _ in range(T)]
    dp = [[0] * (W + 1) for _ in range(T + 1)]

    # bottom_up dp
    dp[1][0], dp[1][1] = jadu[1] % 2, jadu[1] // 2
    for t in range(2, T + 1):
        for w in range(W + 1):
            j = jadu[t] % 2 if w % 2 == 0 else jadu[t] // 2
            dp[t][w] = max(dp[t - 1][0:w + 1]) + j
    print(max(dp[-1]))