[17069번] 파이프 옮기기 2

문제 출처 :

 

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

 

 

 

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

3차원 dp를 이용하여 문제를 해결 할 수 있다.

 

i,j 좌표의 대각선으로 갈 수 있는 것은 결국 i-1,j-1에서 가로,대각선,세로 방향으로 있던 모든 것들이 올 수 있고

 

i,j 좌표의 가로로 올 수 있는 것은 i,j-1에서의 가로, 대각선 방향이었던 것들

 

i,j 좌표의 세로로 올 수 있는 것은 i-1,j에서의 세로, 대각선 방향들이 올 수 있다.

 

이를 3차원 dp로 나타내면 정답을 구할 수 있다.

 

 

 

 

 

소스 코드 : 

 

#include <iostream>
#include <cstdio>
#include <queue>

typedef long long ll;

using namespace std;

// 가로 0 대각선 1 세로 2
int dy[3] = { 0,1,1 };
int dx[3] = { 1,1,0 };

ll dp[35][35][4];
int arr[35][35];

struct INFO {
	int y, x, dir;
};

int n;
bool chkArr(int y, int x) {
	if (0 <= y && y < n && 0 <= x && x < n && !arr[y][x])
		return true;
	return false;
}
int main() {
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &arr[i][j]);

	dp[0][1][0] = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
            if(arr[i][j] == 1)
                continue;
            
			if (chkArr(i - 1, j - 1) && chkArr(i - 1, j) && chkArr(i, j - 1)) {
				dp[i][j][1] += dp[i - 1][j - 1][0];
				dp[i][j][1] += dp[i - 1][j - 1][2];
				dp[i][j][1] += dp[i - 1][j - 1][1];
			}

			if (chkArr(i, j - 1)) {
				dp[i][j][0] += dp[i][j - 1][0];
				dp[i][j][0] += dp[i][j - 1][1];
			}

			if (chkArr(i - 1, j)){
				dp[i][j][2] += dp[i - 1][j][1];
				dp[i][j][2] += dp[i - 1][j][2];
			}
		}

	printf("%lld\n", dp[n - 1][n - 1][0] + dp[n - 1][n - 1][1] + dp[n - 1][n - 1][2]);

	return 0;
}