백준 10164번: 격자상의 경로

[문제 링크]

10164번: 격자상의 경로

---

O로 표시된 칸이 없을 경우 (첫번째 칸 -> N*M번째 칸 으로 가는 경우의 수) 를 구해주면 되고,

O로 표시된 칸이 있을 경우 (첫번째 칸 -> O로 표시된 칸으로 가는 경우의 수) * (O로 표시된 칸 -> N*M번째 칸으로 가는 경우의 수) 를 구해주면 된다.

---

#include <iostream>
using namespace std;

int N, M, K, memo[15*15][15*15];

int Topdown(int start, int end)
{
	if (start >= end) return start == end ? 1 : 0;

	int& ret = memo[start][end];
	if (ret != 0) return ret;

	if(start%M != 0)
		ret += Topdown(start + 1, end);

	ret += Topdown(start + M, end);

	return ret;
}

int main(void)
{
	cin >> N >> M >> K;

	if (K == 0)
		cout << Topdown(1, N*M) << endl;
	else
		cout << Topdown(1, K) * Topdown(K, N*M) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 100 day