[백준/BOJ] 백준 23083번 : 꿀벌 승연이

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

23083번: 꿀벌 승연이

 

다이나믹 프로그래밍을 이용해 cache[x][y]에 (x, y)에서 (n, m) 위치로 가는 경우의 수를 저장해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
int k;
int hole[1005][1005];
vector<vector<long long>> cache(1005, vector<long long>(1005, -1));

long long solve(int x, int y) {

	if (x > n || y > m || x < 1 || y < 1) {
		return 0;
	}
	if (hole[x][y] == 1) {
		return 0;
	}

	if (x == n && y == m) {
		return 1;
	}

	long long& ret = cache[x][y];

	if (ret != -1) {
		return ret;
	}

	ret = 0;

	//아래쪽으로 갈 때
	ret = (ret + (solve(x + 1, y) + 1000000007) % 1000000007);


	//오른쪽 위로 갈 때
	if (y % 2 == 1) {
		ret = (ret + (solve(x - 1, y + 1) + 1000000007) % 1000000007);
	}
	else {
		ret = (ret + (solve(x, y + 1) + 1000000007) % 1000000007);
	}


	//오른쪽 아래로 갈 때
	if (y % 2 == 1) {
		ret = (ret + (solve(x, y + 1) + 1000000007) % 1000000007);
	}
	else {
		ret = (ret + (solve(x + 1, y + 1) + 1000000007) % 1000000007);
	}


	return ret % 1000000007;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

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

	for (int i = 0; i < k; i++) {
		int x, y;
		cin >> x >> y;
		hole[x][y] = 1;
	}

	cout << solve(1, 1);

	return 0;
}