[백준] 1577-도로의 개수(C++)

문제풀이:www.acmicpc.net/problem/1577

1577번: 도로의 개수

 

특이한 dp 문제입니다. 

일반적으로 0,0에서 n,m으로 이동할때 2방향으로만 이동가능하다면 

dp[i][j] = dp[i-1][j] + dp[i][j-1] 입니다.

 

하지만 이문제에서는 이동할 수 없는 구간들이 있습니다. 

 

그렇기 때문에 이러한 부분은 표시해주어야 합니다.

저는 bool construction[201][201] 배열을 통해서 해결했습니다.

construction[b+d][a+c] = 1 값을 저장해주면서 진행했습니다.

 

이때 dp[i][j]는 

 

if (construction[2 * i - 1][2 * j] == 0)
   dp[i][j] += dp[i - 1][j];
if (construction[2 * i][2 * j - 1] == 0)
   dp[i][j] += dp[i][j - 1];

 

입니다.

 

 

아래는 정답코드입니다.

#include <iostream>
using namespace std;

int n = 0, m = 0, k = 0;
int a, b, c, d;
bool construction[201][201] = { 0, };
unsigned long long dp[101][101] = { 0, };
int y_ar[2] = { 0,-1 };
int x_ar[2] = { -1,0 };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	cin >> k;

	for (int i = 0; i < k; i++) {
		cin >> a >> b >> c >> d;
		construction[b + d][a + c] = 1;
	}
	dp[0][0] = 1;

	for (int i = 1; i <= m; i++) {
		if (construction[2 * i - 1][0] == 1)
			break;
		dp[i][0] = 1;
	}
	for (int i = 1; i <= n; i++) {
		if (construction[0][2 * i - 1] == 1)
			break;
		dp[0][i] = 1;
	}


	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (construction[2 * i - 1][2 * j] == 0)
				dp[i][j] += dp[i - 1][j];
			if (construction[2 * i][2 * j - 1] == 0)
				dp[i][j] += dp[i][j - 1];


		}
	}

	cout << dp[m][n] << endl;
	return 0;
}