백준 2240 [자두나무] 파이썬

https://www.acmicpc.net/problem/2240

 

# 백준 2240 자두나무
import sys
T,W=map(int,sys.stdin.readline().split())
ans=[[[0 for _ in range(W+1)] for _ in range(T+1)]for _ in range(3)]
w=W
for i in range(T):
    f_pos=int(sys.stdin.readline())
    if i!=0: # index가 0이 아닌경우
        if f_pos==1: #1번 나무로 떨어지는 경우
            ans[1][i][W]=ans[1][i-1][W]+1 # 1번 나무에 쭉 가만히 있는 경우
            for w in range(W-1,-1,-1): 
                ans[1][i][w]=max(ans[1][i-1][w],ans[2][i-1][w+1])+1
                ans[2][i][w]=ans[2][i-1][w] 
        else: #2번 나무로 떨어지는 경우
            for w in range(W-1,-1,-1):
                ans[2][i][w]=max(ans[2][i-1][w],ans[1][i-1][w+1])+1
                ans[1][i][w]=ans[1][i-1][w]
    else: # index가 0일 때
        if f_pos==1: 
            ans[1][i][w]=1
        elif w>0:
            ans[2][i][w-1]=1
answer=0
for i in range(3):
    for j in range(T+1):
        answer=max(answer,max(ans[i][j]))

print(answer)

BFS에서 비슷한 문제가 있어 그 문제를 떠올려 해결하였다. 

나무 위치와 W를 배열로 잡는 것이 핵심이었다.