[C/C++] 백준 - 5569번 : 출근 경로

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

5569번: 출근 경로

예제 1의 경우 다음과 같은 5가지 경로가 있다.

 

전형적인 경로 탐색의 경우의 수를 파악하는 문제이다. 역시나 메모이제이션 - 동적계획법으로 실행 시간을 줄일 수 있다. 

하지만 경로를 뻗어나가는데 있어 방향만 고려해야하는 것이 아닌 방향이 바뀌었을 경우 바로 다음 경우에는 방향 전환이 불가능하다. 즉, 방향 전환을 한 이후 최소 1번은 더 같은 방향으로 나아가야한다.

 

위 경우까지 고려하여 메모이제이션을 적용시켜준다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 100000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int W, H;
int cache[103][103][2][2];

void input() {
	cin >> W >> H;
}

bool isValid(int y, int x) {
	return (1 <= y && y <= H && 1 <= x && x <= W);
}

// dir -> 0 : 남
// dir -> 1 : 동
// 4번째 매개변수는 교차로에서 방향을 바꾼 것
int path(int y, int x, int dir, int chk) {
	if (y == H && x == W) return 1;
	if (!isValid(y, x)) return 0;
	int& ret = cache[y][x][dir][chk];
	if (ret != -1) return ret;
	
	ret = 0;
	if (chk == 1) {
		if (dir == 0) ret += path(y + 1, x, dir, 0) % Mod;
		else ret += path(y, x + 1, dir, 0) % Mod;
	}
	else {
		if (dir == 0) ret += (path(y + 1, x, dir, 0) + path(y, x + 1, 1, 1)) % Mod;
		else if (dir == 1) ret += (path(y, x + 1, dir, 0) + path(y + 1, x, 0, 1)) % Mod;
		else ret += (path(y + 1, x, 0, 0) + path(y, x + 1, 1, 0)) % Mod;
	}
	return ret;
}

int solution() {
	memset(cache, -1, sizeof(cache));
	return path(1, 1, -1, 0);
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}