1890번: 점프

Memo

문제 설계

이차원 dp배열을 하나 둬서, 그 칸을 밟은 경우 dfs를 돌려서 값을 업데이트하고 다시 그 칸을 방문할 경우 dfs를 돌지 않아도 되는 점을 이용합니다. 어렵지 않았지만 그 칸을 밟았을때 가능성이 없는 경우도 체크해야 한다는 점, int로는 dp배열의 각 값을 모두 담을 수 없다는 점이 까다로웠습니다.

Code

제출 날짜

2021/03/06

메모리

2156 KB

시간

0 ms

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;

std::vector<std::vector<int> >board;
std::vector<std::vector<ll> >dp;
std::vector<std::pair<int, int> >dir;
int N;
ll ans;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> N;
	board.resize(N, std::vector<int>(N));
	size_t _N = N;
	for (size_t i = 0 ; i < _N ; i++)
		for (size_t j = 0 ; j < _N ; j++)
			std::cin >> board[i][j];
	dp.resize(N, std::vector<ll>(N));
	dir = {{1, 0}, {0, 1}};
	ans = 0;
}

ll dfs(int y, int x)
{
	if (dp[y][x] > 0)
		return (dp[y][x]);
	if (dp[y][x] == -1)
		return (0);
	if (y == N - 1 && x == N - 1)
		return (1);
	for (size_t i = 0 ; i < dir.size(); i++)
	{
		int d_y = y + dir[i].first * board[y][x];
		int d_x = x + dir[i].second * board[y][x];
		if (d_y >= N || d_x >= N || (d_y == y && d_x == x))
			continue;
		dp[y][x] += dfs(d_y, d_x);
	}
	if (dp[y][x] == 0)
		dp[y][x] = -1;
	return (dp[y][x] != -1 ? dp[y][x] : 0);
}

void solve()
{
	if (board[0][0] < N)
	{
		ans = dfs(0, board[0][0]);
		ans += dfs(board[0][0], 0);
	}
}

void print_val()
{
	std::cout << ans << std::endl;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}