문제 풀이

3차원 배열을 선언한다.
d[i][j][k] 에서 i,j,k 각각은 i초에 j번 움직였을경우에 k에 위치해 있다는 뜻이다.

i초에 1번에서 자두가 떨어질 경우에는
1번 위치에 있을 경우는 i-1초에 1번에 있을 경우와 i-1초에 2번에있다가 1번으로 왔다는 것으로
$d[i][j][1] = max(d[i-1][j][1] + 1, d[i-1][j-1][2] + 1)$이 되고.
2번 위치에 있을 경우는 i-1초에 1번에 있을경우와 i-1초에 2번에 그대로 있는 경우인데 이 경우에는 자두를 먹을 수 없다.
$d[i][j][2] = max(d[i-1][j][2], d[i-1][j-1][1]$

i초에 2번에서 자두가 떨어질 경우는 마찬가지로
$d[i][j][1] = max(d[i - 1][j][1], d[i - 1][j - 1][2])$
$d[i][j][2] = max(d[i - 1][j][2] + 1, d[i - 1][j - 1][1] + 1)$ 가 된다.

j가 0일때는 움직이지 않았다는 뜻으로
1번 자리에 자두가 떨어질 때에는 d[i][0][1] = d[i-1][0][1] + 1
2번 자리에 자두가 떨어질 때에는 d[i][0][1] = d[i-1][0][1] 로 해준다.

문제 링크

boj/2240

소스코드

PS/2240.cpp

#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<memory.h>
using namespace std;

int d[1001][32][3];
int arr[1001];
int main() {
	int T, W;
	cin >> T >> W;
	for (int i = 1; i <= T; i++)
	{
		cin >> arr[i];
	}
	
	for (int i = 1; i <= T; i++)
	{
		for (int j = 0; j <= W; j++)
		{
			if (arr[i] == 1)
			{
				if (j == 0)
					d[i][0][1] = d[i - 1][0][1] + 1;
				else
				{
					d[i][j][1] = max(d[i - 1][j][1] + 1, d[i - 1][j - 1][2] + 1);
					d[i][j][2] = max(d[i - 1][j][2], d[i - 1][j - 1][1]);
				}
			}
			else
			{
				if (j == 0)
					d[i][0][1] = d[i - 1][0][1];
				else {
					d[i][j][1] = max(d[i - 1][j][1], d[i - 1][j - 1][2]);
					d[i][j][2] = max(d[i - 1][j][2] + 1, d[i - 1][j - 1][1] + 1);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= W; i++)
	{
		ans = max(d[T][i][1], d[T][i][2]);
	}
	cout << ans;
}