[BOJ] 17069 : 파이프 옮기기 2 - travelbeeee

문제 : https://www.acmicpc.net/problem/17069

---

[ 알고리즘풀이 ]

파이프 옮기기 1과 동일하나 long long 배열로 선언해줘야한다.

( 파이프 옮기기 1 풀이 : https://travelbeeee.tistory.com/277 )

#include<iostream>

int N, map[33][33] = {};
long long dp[3][33][33] = {};

using namespace std;

bool check(int x, int y) {
	if (1 <= x && x <= N && 1 <= y && y <= N && map[x][y] == 0)
		return true;
	return false;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];
	dp[0][1][2] = 1;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++) {
			if (check(i, j - 1) && check(i, j))
				dp[0][i][j] += dp[0][i][j - 1] + dp[2][i][j - 1];
			if (check(i - 1, j) && check(i, j))
				dp[1][i][j] += dp[1][i - 1][j] + dp[2][i - 1][j];
			if (check(i - 1, j - 1) && check(i - 1, j) && check(i, j - 1) && check(i, j))
				dp[2][i][j] += dp[0][i - 1][j - 1] + dp[1][i - 1][j - 1] + dp[2][i - 1][j - 1];
		}
	}

	cout << dp[0][N][N] + dp[1][N][N] + dp[2][N][N];

	return 0;
}

---