[알고리즘] C++ 백준 2240 자두나무

 

백준 2240

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

2240번: 자두나무

풀이 전 나의 생각

자두가 정해진 이동 횟수에 따라 자두나무에서 얻을 수 있는 최대 자두 개수를 구하는 문제다.

자두가 1초 안에 움직일 수 있기 때문에 1초마다 자두가 떨어지는 나무가 테스트 케이스로 주어진다.

 

그럼 자두가 어느시간에 도착했을 때 얻을 수 있는 최대의 자두 개수를 구해야 한다. 

그럼 자두가 30번의 횟수 안에 어떤 나무 앞에 있으면서 몇초 때 최대값을 얻을 수 있는지 알아야 하기 때문에

DP의 기초 공간을 DP[31(30번의 이동 횟수)][2(나무의 종류)][1001(최대 시간)]으로 설정해 놓는다.

 

다음으로 정해진 횟수를 처음부터 돌면서 W번째 횟수에서 얻을 수 있는 최대값들을 구해놔야 횟수가 증가하면서 이전값들을 참조할 수 있을 것이다.

 

그럼 이를 구하기 위해선 DP[현재 이동 횟수][나무의 종류][시간] = max(움직이지 않았을 때 + 현재 나무에서 자두를 얻을 수 있는지, 움직였을 때 + 현재 나무에서 자두를 얻을 수 있는지) 확인해주고 최대값을 반환해주면된다.

예를 들어 현재 이동 횟수는 1이고 자두가 3초에 첫 번째 나무 앞에 있다고 가정하면 움직이지 않았을 때 이전의 최대값인 DP[1][0][2 (3초 - 1초)] 와 움직였을 때 최대값인 DP[0(1 - 1)][1][2(3초 - 1초)]을 구분지어 구해줘야 한다. 움직였을 때 이동횟수를 하나 줄인 이유는 이전에 움직여서 현재 이동 횟수가 1이 됐기 때문이다.

 

이런 형식으로 자두가 두 번째 나무 앞에 있을 경우도 같이 구해주면 각 횟수마다 어떤 나무앞에서 최대값을 가지고 있는지 모두 구할 수 있기 때문에 최종적으로 얻을 수 있는 자두의 최대 개수를 구할 수 있다. 

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>


using namespace std;

int t_list[1001];
int dp[31][2][1001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t, w, res = 0;
	cin >> t >> w;

	for (int i = 1; i <= t; i++)
	{
		cin >> t_list[i];
	}

	for (int i = 0; i <= w; i++)
	{
		for (int j = 1; j <= t; j++)
		{
			if (i == 0)
			{
				dp[i][0][j] = dp[i][0][j - 1] + (t_list[j] == 1);
			}
			else
			{
				dp[i][0][j] = max(dp[i][0][j - 1] + (t_list[j] == 1), dp[i - 1][1][j - 1] + (t_list[j] == 1));

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

	for (int i = 0; i < 2; i++)
	{
		for (int j = 0; j <= w; j++)
		{
			res = max(dp[j][i][t], res);
		}
	}
	cout << res;
}