[백준 02240] 자두나무 [Python]

문제

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

---

풀이

T만큼의 시간동안 최대 W만큼 이동하며 가능한 많은 자두를 먹는 문제다.

기준이 2개인 만큼 문제를 단순화 시켜보다.

dp[t][w] : t초에 w번 움직였을 때 받는 자두의 최대 갯수

 

우선, 담는 자두를 고려하지 않고 단순히 시간의 증가에 따라 위 점화식을 성립 시켜보자.

w = 0일 때, dp[t][0] = dp[t - 1][0]이 성립한다.

이제 자두를 담아보자.

 

처음 자두의 위치는 1번 나무이므로 이동횟수 w가 홀수 이면 2번나무, 짝수이면 다시 1번 나무에 위치함을 의미한다.

매 t초마다 자두가 떨어지는 나무의 위치에 따라, 이동 횟수가 0일 때 받은 자두 횟수를 갱신해주자.

 

마찬가지로 이제는 다른 나무로 움직이는 경우를 생각해보자.

이동 횟수 1 ~ W에 대해 1초 전과 비교해 움직였거나( dp[t - 1][w - 1] ), 움직이지 않은 경우( dp[t - 1][w] )중에 받은 자두 최대 갯수를 선택하면 된다.

움직이지 않은 경우( w = 0)을 먼저 계산한 이유는 w = 1일 때를 처리하기 위함이다.

이동 횟수( w )에 따라 자두가 위치한 나무가 다르다. 또한, 위치한 나무에 자두가 담을 수 있는 자두가 있거나 없을 수 있다.

 

이제 마찬가지로 움직이면서 자두를 담는 경우를 생각해보자.

떨어지는 자두( jadu[i] )를 2로 나누었을 때의 몫과 나머지를 활용해 계산할 수 있다.

• w is odd, jadu[t] = 1 : 2번 나무에 위치할 때, 자두는 1번 나무에 떨어진다. jadu[t] // 2 = 0
• w is odd, jadu[t] = 2 : 2번 나무에 위치할 때, 자두는 2번 나무에 떨어진다. jadu[t] // 2 = 1
• w is even, jadu[t] = 1 : 1번 나무에 위치할 때, 자두는 1번 나무에 떨어진다. jadu[t] % 2 = 1
• w is even, jadu[t] = 2 : 1번 나무에 위치할 때, 자두는 2번 나무에 떨어진다. jadu[t] % 2 = 0

항상 W가 많은 경우가 자두를 최대로 담은 경우는 아니다. 최댓값을 출력해주자.

---

소스코드

보기

---

출처

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