[ boj : 14722 ] 우유 도시

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

14722번: 우유 도시

해설 : 딸기우유->초코우유->바나나우유 순으로 먹어야 되는데, 꼭 인접한 위치에 있는 우유를 먹을 필요가 없습니다. 따라서 단순한 2차원 테이블로는 해결할 수가 없죠. 

 

바로 위의 우유를 마지지 않더라도 지금까지 먹은 우유중에 가장 최근에 먹은 우유가 순서에 적합하다면 카운트를 시켜줘야 하니까요. 따라서 3차원 테이블로 이를 표현할 수 있습니다.

 

dp[i][j][k] = (i,j)에 위치하고 지금까지 먹은 우유 중 가장 최근에 마신 우유가 k 일때 최대값

 

그러면 현재 내가 딸기우유가 위치해 있는 좌표에 도달했다면 MAX(지금까지 가장 최근에 딸기우유를 마셨을때 최대값, 지금까지 바나나우유를 최근에 마셨을때 최대값 +1 ) 이 되겠네요.

 

#include<bits/stdc++.h>

using namespace std;

int n;
int board[1000][1000],dp[1000][1000][3];

int go(int x, int y);

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
			if (board[i][j] == 0) 
				dp[i][j][0] = 1;			
		}	
	
	for(int i=0;i<n;i++)
		for (int j = 0; j < n; j++) {
			if (i == 0) {
				dp[i][j][0] = max(dp[i][j][0], dp[i][j - 1][0]);
				dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][1]);
				dp[i][j][2] = max(dp[i][j][2], dp[i][j - 1][2]);

				if (board[i][j] == 0) {					
					if (dp[i][j - 1][2] != 0)dp[i][j][0] = max(dp[i][j][0], dp[i][j - 1][2] + 1);
				}
				else if (board[i][j] == 1) {
					if (dp[i][j - 1][0] != 0)dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][0] + 1);
				}
				else {
					if (dp[i][j - 1][1] != 0)dp[i][j][2] = max(dp[i][j][2], dp[i][j - 1][1] + 1);
				}
			}
			else if (j == 0) {
				dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][0]);
				dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][1]);
				dp[i][j][2] = max(dp[i][j][2], dp[i - 1][j][2]);

				if (board[i][j] == 0) {
					if (dp[i - 1][j][2] != 0)dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][2] + 1);
				}
				else if (board[i][j] == 1) {
					if (dp[i - 1][j][0] != 0)dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][0] + 1);
				}
				else {
					if (dp[i - 1][j][1] != 0)dp[i][j][2] = max(dp[i][j][2], dp[i - 1][j][1] + 1);
				}
			}
			else {
				dp[i][j][0] = max(dp[i][j][0], max(dp[i - 1][j][0], dp[i][j - 1][0]));
				dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j][1], dp[i][j - 1][1]));
				dp[i][j][2] = max(dp[i][j][2], max(dp[i - 1][j][2], dp[i][j - 1][2]));

				if (board[i][j] == 0) {
					if (dp[i - 1][j][2] != 0)dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][2] + 1);
					if (dp[i][j - 1][2] != 0)dp[i][j][0] = max(dp[i][j][0], dp[i][j - 1][2] + 1);
				}
				else if (board[i][j] == 1) {
					if (dp[i - 1][j][0] != 0)dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][0] + 1);
					if (dp[i][j - 1][0] != 0)dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][0] + 1);
				}
				else {
					if (dp[i - 1][j][1] != 0)dp[i][j][2] = max(dp[i][j][2], dp[i - 1][j][1] + 1);
					if (dp[i][j - 1][1] != 0)dp[i][j][2] = max(dp[i][j][2], dp[i][j - 1][1] + 1);
				}
			}
		}
	cout << max(dp[n - 1][n - 1][0], max(dp[n - 1][n - 1][1], dp[n - 1][n - 1][2]));
	return 0;
}