백준 2240 - 자두나무

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 T개의 자두가 1혹은 2에서 떨어질 때 받을 수 있는 자두의 최대 개수를 구하는 것이다.

자두를 받으려면 1혹은 2자리에 위치해야 하며 최대 W만큼 이동할 수 있다.

 

문제를 보는 순간 DP를 사용해야 한다는 느낌이 온다.

그럼 DP에서 관리할 값은 당연히 받을 수 있는 최대 개수일 것인데 축을 어떻게 설정해야 하는지 결정해야 한다.

 

해당 문제에서 중요한 변수는 T와 W는 명백하다.

그리고 하나 더 현재 자신의 위치 또한 관리해야 할 값이다.

따라서 DP에서 3차원 축을 담당하는 것은 T, W, 현재 위치이다.

 

그럼 이제 DP를 채우는 방법을 알아 보자.

해당 문제는 w번 이동할 수 있다고 가정한 후 DP를 채워나가면 된다.

0번 이동할 수 있을 때, 1번 이동할 수 있을 때, 2번.. 이런 방식으로 채워나가면 된다.

1번 이동할 수 있는 경우는 0번 이동할 수 있는 경우에서 구한 최적해를 이용하여 구할 수 있기 때문이다.

 

그리고 T와 자신의 위치를 비교하면 현재 떨어지는 자두를 받을 수 있는지 확인할 수 있다.

i번째 자두가 1이고 자신의 위치가 1이라면 이동 없이 자두를 받을 수 있고 이전 2에 있던 위치에서 w를 하나 소모하여 1로 이동 후 받을 수도 있다.

반대의 경우도 마찬가지이다. (j = 이동 횟수, i = 자두)

// dp[이동][위치][자두]
int dp[31][2][1001];

dp[j][0][i] = max(dp[j][0][i - 1] + (plums[i] == 1), dp[j - 1][1][i - 1] + (plums[i] == 1));
dp[j][1][i] = max(dp[j][1][i - 1] + (plums[i] == 2), dp[j - 1][0][i - 1] + (plums[i] == 2));

단, j가 0일 때는 이동할 수 없기 때문에 시작 위치인 1에 대한 값들만 기록하면 된다.

if (j == 0)
{	
    dp[j][0][i] = dp[j][0][i - 1] + (plums[i] == 1);
}

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int T, W;
vector<int> plums;
int dp[31][2][1001];

int main()
{
	INPUT_OPTIMIZE;

	cin >> T >> W;
	plums.resize(T + 1);
	
	for (int i = 1; i <= T; i++)
	{
		cin >> plums[i];
	}

	for (int j = 0; j <= W; j++)
	{
		for (int i = 1; i <= T; i++)
		{
			if (j == 0)
			{	
				dp[j][0][i] = dp[j][0][i - 1] + (plums[i] == 1);
			}
			else
			{
				dp[j][0][i] = max(dp[j][0][i - 1] + (plums[i] == 1), dp[j - 1][1][i - 1] + (plums[i] == 1));
				dp[j][1][i] = max(dp[j][1][i - 1] + (plums[i] == 2), dp[j - 1][0][i - 1] + (plums[i] == 2));
			}
		}
	}


	int ans = 0;
	for (int i = 0; i < 2; i++)
	{
		for (int j = 0; j <= W; j++)
		{
			ans = max(ans, dp[j][i][T]);
		}
	}

	cout << ans << '\n';


	return 0;
}

---