백준 17069 파이프 옮기기2, 17070 파이프 옮기기1

#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <utility>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>

using namespace std;
typedef long long lld;

int N;
int arr[32][32];

lld memo[32][32][3];

lld dp(int i, int j, int mode) {
	if (i < 0 || i > 31 || j < 0 || j > 31) {
		return 0;
	}
	lld& m = memo[i][j][mode];
	if (m != -1) return m;
	if (i == 0 && j == 1 && mode == 0) {
		m = 1;
		return m;
	}
	else if (i == 1 && j == 1 && mode == 1) {
		m = 0;
		return m;
	}
	else if (i == 1 && j == 0 && mode == 2) {
		m = 0;
		return m;
	}

	switch (mode) {
	case 0:
		if (arr[i][j] == 0) {
			lld s1 = dp(i, j - 1, 1);
			lld s2 = dp(i, j - 1, 0);
			return m = s1 + s2;
		}
		break;
	case 1:
		if (i - 1 < 0 || j - 1 < 0) break;
		else if (arr[i][j] == 0 && arr[i - 1][j] == 0 && arr[i - 1][j - 1] == 0) {
			lld s1 = dp(i - 1, j - 1, 0);
			lld s2 = dp(i - 1, j - 1, 1);
			lld s3 = dp(i - 1, j - 1, 2);
			return m = s1 + s2 + s3;
		}
		break;
	case 2:
		if (arr[i][j] == 0) {
			lld s1 = dp(i - 1, j, 1);
			lld s2 = dp(i - 1, j, 2);
			return m = s1 + s2;
		}
		break;
	}
	return 0;
}

int main() {

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &arr[i][j]);
			for (int k = 0; k < 3; k++) {
				memo[i][j][k] = -1;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (arr[i][j] == 1) {
				if (j - 1 >= 0) {
					memo[i][j][0] = 0;
					if (i - 1 >= 0) {
						memo[i][j][1] = 0;
					}
				}
				if (i - 1 >= 0) {
					memo[i][j][2] = 0;
				}

				if (j + 1 < N) {
					memo[i][j+1][0] = 0;
					if (i + 1 < N) {
						memo[i + 1][j + 1][1] = 0;
					}
				}
				if (i + 1 < N) {
					memo[i + 1][j][2] = 0;
				}

				if (j + 1 < N && i - 1 >= 0) {
					memo[i][j + 1][1] = 0;
				}
				if (i + 1 < N && j - 1 >= 0) {
					memo[i + 1][j][1] = 0;
				}

			}
		}
	}

	lld s1 = dp(N - 1, N - 1, 0);
	lld s2 = dp(N - 1, N - 1, 1);
	lld s3 = dp(N - 1, N - 1, 2);
	cout << s1 + s2 + s3 << endl;

	return 0;
}

DP[i][j][mode]는 "파이프를 i, j로 옮길 수 있는 총 가지수. 단, 파이프의 최종 형태가 mode의 형태여야 함." 이라는 뜻이다

mode는 파이프의 3가지 형태를 의미하는데

0일 경우 가로

1일 경우 대각선

2일 경우 세로

의 형태로 파이프가 놔둬진 것을 의미한다.

dp로 풀기 전에 전처리를 한번 하는데

1이 있는 부분에 대해서, 그 1을 포함하게 놔둬지는 파이프에 대해 전부 memo에 0을 넣는다.

(즉, 못 놔둔다는 뜻)

또한 대각선으로 놔둬질 때, 벽(1)때문에 못놔둬지는 곳도 memo를 0으로 한다.