[백준/Python] 2240 자두나무

문제링크

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

2240번: 자두나무

---

 

코드

t,w = map(int,input().split())
data = [0] + [int(input()) for _ in range(t)]
dp = [[0 for _ in range(w+1)] for _ in range(t+1)]
for i in range(1,t+1):
    if data[i]==1:
        dp[i][0] = dp[i-1][0]+1
    else:dp[i][0] = dp[i-1][0]
    
    for j in range(1,w+1):
        if (data[i]==1 and j%2==0) or (data[i]==2 and j%2!=0):
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])
print(max(dp[t]))

---

 

문제풀이

dp[i][j]는 i초 지났을 때, j 번 움직여서 먹을 수 있는 최대 자두 수를 의미한다.

j==0일 때, 즉 한 번도 움직이지 않았을때 1번 나무에서 떨어지는 자두만 먹을 수 있다. i초에 1번 나무에서 자두가 떨어지면 자두를 먹을 수 있으므로 dp[i][0] = dp[i-1][0]+1, i초에 2번 나무에서 자두가 떨어지면 자두를 먹을 수 없으므로 dp[i][0] = dp[i-1][0]

1~w번 움직일 때, 자두를 먹을 수 있는 조건은

1.1번 나무에서 자두가 떨어질 때, 짝수번 움직인 경우(j%2==0)

2.2번 나무에서 자두가 떨어질 때, 홀수번 움직인 경우(j%2!=0)

두 가지 경우이다.

위 경우는 움직이고 자두를 받아먹을지, 안움직이고 제자리에서 자두를 받아먹을지를 생각하면 된다.( dp[i][j] = max(dp[i-1[j], dp[i-1][j-1])+1 )

두 가지 경우를 제외하면 자두를 받아먹을 수 없으므로 움직일지, 안움직일지만 생각하면 된다.( dp[i][j] = max(dp[i-1[j], dp[i-1][j-1]) )