[백준-2240] 자두나무 🍒

❓ Problem

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.
매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.
자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

🤔 How

dp 점화식을 구하기 까다로웠던 문제 😅
이동할수있는 횟수와 자두나무 두가지 경우를 생각해야하기에 최소 2차원 DP를 고려해야한다.

자두(사람) 이 떨어지는 자두를 받으려면 주어진 리스트에서 해당 번호의 나무에 있어야한다.
또 이동시간을 고려하지 않으므로 다음 자두가 떨어질때까지 이동을하게된다면 충분히 받을 수 있다.

고려해야할점

1. 각 자두가 떨어지는 순서 (t) 를 고려하여 현재 몇번째 이동 기회 (w) 인지 최소 2차원 배열이 필요하다.

• 모든경우의 dp를 생성할수 있겟지만 최적화를 고려하여 2차원 DP배열을 조금 더 메모리 최적화 하였다.
• DP 테이블은 이전테이블을 참조하므로 모든 이동 기회에대한 row를 생성하는것이아닌 이전 DP테이블과 갱신한 DP 테이블
  2개로 해결하기위해 최적화 하였다.

2. 자두가 떨어지는시간이 이동기회(w) 부터 시작하는 이유

• 이전 이동 기회에서 (w-1) 까지 DP 테이블이 최적화되어있기때문에 lsit[:w-1] 부분은 새로 갱신할 필요가없다 그래서 갱신이 필요한 테이블만 갱신하도록 최적화 하엿다.

최적화

❗ Solve

# 자두나무
import sys
input =sys.stdin.readline

def solution():
    T,W=map(int,input().split())
    plums=[0]+[int(input()) for _ in range(T)]
    dp=[[0,0] for _ in range(T+1)]

    # init DP
    for i in range(1,len(plums)):
        dp[i][0]=dp[i-1][0]+1 if plums[i]%2 else dp[i-1][0]

    for w in range(1, W+1): # 자리 바꾸는 기회
        for t in range(w,T+1): # 자두가 떨어지는 시간
            if w%2 : #홀수번째 이동 일때는 2번나무에서 자두를 받을수있음
                if not plums[t]%2: # 2번 나무 떨어지는 경우
                    dp[t][1]=max(dp[t-1])+1
                else:
                    dp[t][1]=dp[t-1][1]
            else: #짝수번째 이동
                if plums[t]%2: # 1번나무에서 떨어지는경우
                    dp[t][0]=max(dp[t-1])+1
                else:
                    dp[t][0]=dp[t-1][0]
    print(max(dp[-1]))

    pass
if __name__=="__main__": # 실행되는 부분
    solution()
    pass