[백준] 17069번 파이프 옮기기2 [C++]

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

17069번: 파이프 옮기기 2

---

문제 설명

 

ㄴ

 

 

---

접근 방식

다이나믹 프로그래밍 방법으로 해결하였다.

먼저 DP라는 배열을 만들어줄건데, 이는 x 좌표, y 좌표 , 그리고 현재 놓여진 파이프의 모양이 3가지 정보가 담겨져 있다.

나는 파이프가 세로로 놓였을때를 0, 가로로 놓였을때를 1,대각선으로 놓였을때를 2로 할건데

이를 점화식으로 나타낸다면

DP[X][Y][0] -> DP[X-1][Y][0]+DP[X-1][Y][2] 

DP[X][Y][1] -> DP[X][Y-1][1]+DP[X][Y-1][2] 

DP[X][Y][2] -> DP[X-1][Y-1][0]+DP[X-1][Y-1][1]+DP[X-1][Y-1][2]

(단 벽에 막히지 않을 경우) 가 된다.

문제에서 언급한 대로, 맨 처음엔 가로로 놓여진 파이프가 있으니  DP[1][2][1]=1 로 정해놓고 연산을 시작하면, 우리가 원하는 DP[N][N]까지의 3가지 경우를 모두 구할 수 있다.

---

코드

#include <iostream>
#include<queue>
#include<vector>
#include<tuple>
#include<cmath>
using namespace std;
int n;
long long dp[33][33][3];
int arr[33][33];
long long dpf(int x, int y, int t) {
	if (dp[x][y][t] != -1)return dp[x][y][t];
	if (arr[x][y] == 1)return 0;//현재위치가 벽이라면 0을 반환
	if (t == 0) {	//파이프가 세로일 경우
		dp[x][y][t] = dpf(x - 1, y, 0)+ dpf(x - 1, y, 2);
		
	}
	if (t == 1) {   //파이프가 가로일 경우
		dp[x][y][t] = dpf(x , y-1, 1) + dpf(x, y-1, 2);
	}
	if (t == 2) {	//파이프가 대각선일 경우
		if (arr[x - 1][y] == 1)return 0; //대각선에 걸칠 경우가 벽일경우
		if (arr[x][y - 1] == 1)return 0;
		dp[x][y][t] = dpf(x - 1, y - 1, 0) + dpf(x - 1, y - 1, 1) + dpf(x - 1, y - 1, 2);
	}
	return dp[x][y][t];
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k <= 2; k++)
				dp[i][j][k] = -1;
			cin >> arr[i][j];
		}
	}
	dp[1][2][1] = 1;
	cout << dpf(n, n,0)+dpf(n, n, 1)+ dpf(n, n, 2);

}

 

---