[백준 C++] 17070 파이프 옮기기 1 - 다이나믹프로그래밍

17070번: 파이프 옮기기 1

#include <iostream>
using namespace std;

int House[16][16];
int DP[16][16][3];

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

	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> House[i][j];
		}
	}

	DP[0][1][0] = 1;
	for (int i = 2; i < N; ++i)
	{
		if (House[0][i] == 1)
		{
			break;
		}

		DP[0][i][0] = 1;
	}

	for (int i = 1; i < N; ++i)
	{
		for (int j = 2; j < N; ++j)
		{
			if (House[i][j] == 1)
			{
				continue;
			}

			DP[i][j][0] = DP[i][j - 1][0] + DP[i][j - 1][2];
			DP[i][j][1] = DP[i - 1][j][1] + DP[i - 1][j][2];

			if (House[i - 1][j] == 1
				|| House[i][j - 1] == 1)
			{
				continue;
			}

			for (int k = 0; k < 3; ++k)
			{
				DP[i][j][2] += DP[i - 1][j - 1][k];
			}
		}
	}

	int Sum = 0;
	for (int i = 0; i < 3; ++i)
	{
		Sum += DP[N - 1][N - 1][i];
	}

	cout << Sum;
}

---

 

모든 칸에서 파이프가 놓일 수 있는 경우를 DP 행렬에 저장해주어서 푸는 문제입니다.

 

예시로 (2, 2) 칸에 파이프 앞쪽이 놓여있을 경우는 다음 그림과 같이 나타낼 수 있습니다.

가로로 놓여있는 경우 - DP[2][2][0]: DP[i][j - 1][0] + DP[i][j - 1][2]

세로로 놓여있는 경우 - DP[2][2][1]: DP[i - 1][j][1] + DP[i - 1][j][2]

대각선으로 놓여있는 경우 - DP[2][2][2]: DP[i - 1][j - 1][0] + DP[i - 1][j - 1][1] + DP[i - 1][j - 1][2]

 

이런식으로 점화식을 이용해서 (1, 2) 칸부터 채워주면 됩니다.

 

주의해야할 점은 0번 째 행은 가로로 놓는 경우밖에 없기때문에 조건에 맞게 따로 채워주어야 하고

0번 열과 1번 열은 이동할 수 없는 위치이므로 채울 필요가 없습니다.

 

그리고 DP 값을 채워줄 때 해당 칸에 벽이 존재하지는 않는지,

대각선일 경우에는 해당 칸을 포함해서 왼쪽, 위쪽 칸에도 벽이 존재하지 않는지 체크해주어야 합니다.