[C/C++] 백준 - 14722번 : 우유 도시

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

14722번: 우유 도시

문제

영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다.

입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 

1. 맨 처음에는 딸기우유를 한 팩 마신다.
2. 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.
3. 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.
4. 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 

저번 축제에서 수많은 우유를 마셨지만 더욱 우유에 갈증을 느낀 영학이는 우유 여행을 떠났다.

맛있는 우유를 찾아 떠난 영학이는 수많은 우유 가게로 둘러 쌓인 어느 도시에 도착했다.

이 도시는 정사각형 형태의 2차원 격자 모양으로 남북으로 N개, 동서로 N개, 총 N*N개의 우유 가게들이 있다.

영학이는 도시의 서북쪽 끝 (1, 1)에서 출발해서 동남쪽 아래 (N, N)까지 까지 가면서 우유를 사 마신다. 

각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다.

각각의 우유 가게 앞에서, 영학이는 우유를 사 마시거나, 사 마시지 않는다.

So cooooool~한 영학이는 오직 동쪽 또는 남쪽으로만 움직이기 때문에 한 번 지나친 우유 가게에는 다시 가지 않는다.

영학이가 마실 수 있는 우유의 최대 개수를 구하여라.

 

전형적인 동적계획법으로 해결 가능한 문제 유형이나 전에 풀었던 문제보다는 쪼금 어려운 문제이다.

이유는 고려해야할 경우가

 

1. 우유를 먹을 경우 정해진 순서로 먹어야함 (딸기 -> 초코 -> 바나나 -> 딸기 순)

2. 우유를 꼭 먹어야만 하는 건 아니다. 즉, 정해진 순서에 충족할 때만 진행하는 것이 아닌 순서에 충족하지 않더라도 진행 가능하다. 단, 이 때 우유를 먹는 것은 불가능하다.

 

위 2가지 경우를 고려하여 코드를 작성해야한다.

 

2차원 배열 형태로만 메모이제이션을 적용하면 전 좌표가 어디였는지에 따라 값이 달라질 수도 있으므로 이것을 고려해야한다. 나는 이것을 고려할 때 전 좌표의 숫자가 무엇이었는지를 메모이제이션에 적용시켜주었다.

 

또한, 먹었는지 먹지 않았는지에 따라 경우의 수가 또 달라진다. 그래서 이 부분에 대한 것도 메모이제이션에 적용시켜주었다.

 

그래서 나는 메모이제이션을 적용할 때,

< 2차원 배열 형태 +  현 좌표로 오기 바로 직전 board의 숫자 + 전 위치에서 먹고 왔는지 / 먹고 오지 않았는지 >

위 경우를 모두 따져주었다.

 

주어진 메모리 효율 내 통과가 가능했기에 이렇게 짰지만, 만약 메모리 효율을 통과하지 못했다면 바텀업 방식으로 코드를 작성했어야 할 것 같다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;
// 0 : 딸기, 1 : 초코, 2 : 바나나
int board[1003][1003];
int cache[1003][1003][3][2];

void input() {
	cin >> N;
	memset(cache, -1, sizeof(cache));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> board[i][j];
		}
	}
}

bool judge(int cur, int prev) {
	if (prev == -1) {
		if (cur == 0) return true;
		else return false;
	}
	if (prev == 0 && cur == 1) return true;
	if (prev == 1 && cur == 2) return true;
	if (prev == 2 && cur == 0) return true;
	return false;
}

int path(int y, int x, int prev, int buy) {
	if (y == N && x == N) {
		if (judge(board[y][x], prev)) return 1;
		return 0;
	}
	if (y > N || x > N) return -INF;
	int& ret = cache[y][x][prev][buy];
	if (ret != -1) return ret;
	ret = 0;
	if (judge(board[y][x], prev)) ret = max({ ret, path(y + 1, x, board[y][x], 1) + 1, path(y, x + 1, board[y][x], 1) + 1,
											path(y + 1, x, prev, 0), path(y, x + 1, prev, 0) });
	else ret = max({ ret, path(y + 1, x, prev, 0), path(y, x + 1, prev, 0) });
	return ret;

}

int solution() {
	return path(1, 1, -1, 0);
}

int main() {
	fastio;
	input();
	cout << solution() << endl;
	 
	return 0;
}