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

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

2240번: 자두나무

Problem

매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 최대의 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

조건

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

SOL

자두 나무가 2개 (1번 나무, 2번나무) ,T초동안 떨어진다, W번 움직인다.

완전탐색

안움직이고 먹는게 최대일 수 도 있고, 1번 움직이는게 최대일 수 도 있고, 2번 움직이는게 최대일수도..즉, W까지 모든 움직임 횟수를 다 check해야한다. 완전탐색으로 한다면, 1000초동안 30번 움직이는 경우, 29번 움직이는경우 ... ..0번 움직이는 경우를 다 구해야한다. 1000초동안, 30번 움직이는 경우를 뽑아주는 경우의 수만해도, 1000C30인데, 계산해보면 엄 -청 큰 수가 나온다. 불가능하다.

DP

하지만, 재귀적으로 구현이 되므로, DP로 최적화를 할 수 있는 가능성이 있다.

 

DP[T][W] : T초동안, W 움직였을 때, 먹을 수 있는 최대의 자두의 수

구하는 답 : max(DP[T]) , 몇번을 움직였든, 최대의 자두의 수를 출력

점화식

움직이지 않는 경우

• 1번 나무에서 떨어지는 것만 먹을 수 있다.
• DP[T][0] = if plums[i] ==1 : DP[T-1][0] +1  else: DP[T-1][0]

움직이는 경우 

• 움직여서 자두를 먹거나, 그 자리에서 먹는 2가지 경우가 있다.
• 이때, 움직였는데, 자두를 놓칠 수 도 있다.

이동횟수 

• 짝수 : 1번 나무에 있음.
• 홀수 : 2번 나무에 있음.

T, W =map(int,input().split())
plums=[int(input() for _ in range(T)]
DP= [[0]*(W+1) for _ in range(T)]

for i in range(T):
	for j in range(W+1):
    	if j==0:
        	if plums[i] ==1:
            	DP[i][0] = DP[i-1][0]+1
            else:
            	DP[i][0] = DP[i-1][0]
         else:
         	if plums[i] ==1 and j%2==0:
            	DP[i][j] = max(DP[i-1][j],DP[i-1][j-1])+1
            elif plums[i] ==2 and j%2==1:
            	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[-1]))