[BOJ 2240] 자두나무 C++ 풀이

문제 링크

www.acmicpc.net/problem/2240

2240번: 자두나무

자두나무 성공분류

시간 제한 2 초

메모리 제한 128 MB

제출 8550

정답 2691

맞은 사람 1982

비율 35.393%

문제

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

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

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

입력

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

출력

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

 

풀이

언제나 그렇듯 어려운 DP문제였습니다. 그리고, DP는 접근에 따라 매우 쉬울 수도 있는 문제입니다.

문제에서 아래의 조건을 주의할 필요가 있었습니다.

 

1. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 

2. 자두는 다른 나무 아래로(1초 보다 훨씬 짧은 시간에) 움직일 수 있다.

3. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

 

저는 아래와 같이 DP 배열을 선언하였습니다.

dp[A][B][C] = D  // dp[이동횟수][자두의 위치][흐른 시간] = 받은 자두의 수

최대 이동수가 30, 나무는 2그루, 시간은 최대 1000이므로 dp[31][2][1001]와 같이 초기 배열을 선언할 수 있습니다.

 

dp[이동 횟수][현재위치][i] = 1. "움직이지 않았고, 현재 떨어진 자두가 내 위치인가?" or 2. "움직였고, 현재 떨어진 자두가 내 위치인가?" 중 큰 값을 가지게 됩니다.

이를 수도코드로 옮겨보면,

dp[횟수][나무][i]= max("직전 위치에서 움직이지 않음, 사과받음?" , "직전 위치에서 움직임, 사과받음?" )

과 같이 표현할 수 있습니다.

 

#include <iostream>
#include <algorithm>

using namespace std;
int T, W;

int list[1001];
int dp[31][2][1001];
// dp[이동횟수][현재위치][시간]

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	// 입력
	cin >> T >> W;
	for (int i = 1; i <= T; i++)
		cin >> list[i];


	for (int j = 0; j <= W; j++)
	{
		for (int i = 1; i <= T; i++)
		{
			if (j == 0)
			{	//처음 시작시 자두는 1번 나무 아래 위치해있다.
				dp[j][0][i] = dp[j][0][i - 1] + (list[i] == 1);
			}
			else
			{
				//첫 시작 이후는, 위치 움직임or안움직임, 받음or못받음을 확인하며 체크한다.
				dp[j][0][i] = max(dp[j][0][i - 1] + (list[i] == 1), dp[j - 1][1][i - 1] + (list[i] == 1));
				dp[j][1][i] = max(dp[j][1][i - 1] + (list[i] == 2), dp[j - 1][0][i - 1] + (list[i] == 2));
				// dp[이동횟수][자두의 위치][흐른 시간] = 
				// (이동하지않고 시간만 1초 흐름 + i번째 입력과 현재 위치가 같은가?), 
				// (이동했고, 1초 흐름 + i번째 입력과 현재 위치가 같은가?) 중 큰 값
			}
		}
	}


	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';
}

질문과 잘못된 정보 수정 요청은 언제나 환영합니다. 편하게 댓글을 달아주세요.

오늘도 부족한 제 글을 읽어주셔서 감사합니다.