백준 5569 출근 경로

출근 경로를 구하는 dp 문제입니다.  상근이가 동이나 북쪽으로 이동을 하는데 교차로에서 방향을 변경한 경우 그 다음번에는 방향을 변경 할 수 없습니다. 따라서 상근이의 현재 방향과 방향 전환이 가능한지 여부를 저장해 두어야 합니다.

따라서 dp 식을 dp[i][j][k][l] 로 정하고 (i,j에서 상근이는 l 방향이고 k(방향전환 가능여부) ) 의 의미를 가집니다.

 

따라서 이에 따라 i,j에서 총4가지 경우에 대해 아래와 같이 식을 세울 수 있습니다.

방향전환이 불가능한 경우는 이전칸에서 방향전환을 한 경우이므로 그경우를 넣어주고

방향전환이 가능한 경우는 이전칸에서 방향전환이 가능 / 불가능한 경우 모두 가능하므로 더해서 넣어줍니다.

 

dp[i][j][0][0] = (dp[i - 1][j][0][0] + dp[i - 1][j][1][0])%MOD;
dp[i][j][0][1] = (dp[i][j - 1][0][1] + dp[i][j - 1][1][1])%MOD;
dp[i][j][1][0] = (dp[i - 1][j][0][1])%MOD;
dp[i][j][1][1] = (dp[i][j - 1][0][0])%MOD;

 

아래는 전체 코드입니다.

 

 

#include <iostream>

using namespace std;
#define MOD 100000

int main(void) {

	int w, h; cin >> w >> h;
	int dp[101][101][2][2] = { 0, }; //3,4 번째 인덱스는 방향전환 가능 여부와 내 방향 0->북 1->동

	for (int i = 2; i <= h; i++)
		dp[i][1][0][0] = 1;

	for (int i = 2; i <= w; i++)
		dp[1][i][0][1] = 1;


	for(int i = 2; i <= h; i++)
		for (int j = 2; j <= w; j++) {
			dp[i][j][0][0] = (dp[i - 1][j][0][0] + dp[i - 1][j][1][0])%MOD;
			dp[i][j][0][1] = (dp[i][j - 1][0][1] + dp[i][j - 1][1][1])%MOD;
			dp[i][j][1][0] = (dp[i - 1][j][0][1])%MOD;
			dp[i][j][1][1] = (dp[i][j - 1][0][0])%MOD;
		}

	cout << (dp[h][w][0][0] + dp[h][w][0][1] + dp[h][w][1][0] + dp[h][w][1][1]) % MOD;
	return 0;
}