Memo

어려웠던 점

처음에 완전 탐색으로 풀었는데 시간 초과가 나서 dp로 바꿔 풀었습니다. dp로 풀기 위해서는 파이프가 총 3방향으로 놓일 수 있기 때문에 3차원 배열로 풀어야 한다는 사실을 인지하는 것 까지가 어려웠습니다 (저는 이차원 배열 3개로 . 또한 파이프가 두 칸을 차지하기 때문에 어디에 값을 저장해야 하는지에 대한 고민도 필요했습니다. 삼성 기출문제들은 그냥 막 구현하면 될 것 같지만 생각을 좀 더 해보면 당연한 규칙들이 나오기 때문에 좀 더 깊게 고민해야 하는 것 같습니다.

아쉬웠던 점

이차원 배열을 반복문으로 돌면서 dp를 이용할 수 있는데, 그래프를 통해 풀어서 그런지 시간이 상당히 많이 소요되었습니다.
dfs함수 내에서 코드가 가독성이 떨어졌습니다.

Code

제출 날짜

2021/03/01

메모리

2024KB

시간

664ms

#include <iostream>
#include <vector>

std::vector<std::vector<int> >pipe;
std::vector<std::vector<int> >dp_right;
std::vector<std::vector<int> >dp_down;
std::vector<std::vector<int> >dp_diagonal;
int N;
size_t _N;
int cnt;
std::vector<std::vector<std::pair<int, int> > >g_right_dir;
std::vector<std::pair<int, int> >g_left_dir;

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;
	pipe.resize(N, std::vector<int>(N));
	dp_right.resize(N, std::vector<int>(N));
	dp_down.resize(N, std::vector<int>(N));
	dp_diagonal.resize(N, std::vector<int>(N));
	_N = N;
	for (size_t i = 0 ; i < _N ; i++)
		for (size_t j = 0 ; j < _N ; j++)
			std::cin >> pipe[i][j];
	cnt = 0;
	g_right_dir = {{{0, 1}, {1, 1}},{{1, 0}, {1, 1}}, {{1, 0}, {1, 1}, {0, 1}}};
	g_left_dir = {{0, 1} , {1, 0}, {1, 1}};
}

int dir_check(std::pair<int, int> left, std::pair<int, int> right)
{
	if (right.first == left.first && right.second > left.second)
		return (1);
	else if (right.first > left.first && right.second == left.second)
		return (2);
	else
		return (3);
}

int dir_distribute_right(int a)
{
	if (a == 1)
		return (0);
	else if (a == 2)
		return (1);
	else
		return (2);
}

int dir_distribute_left(int a)
{
	if (a == 1)
		return (0);
	else if (a == 2)
		return (1);
	else
		return (2);
}

int 	dfs(std::pair<int, int> left, std::pair<int, int> right)
{
	if (right.first >= N || right.second >= N || pipe[right.first][right.second])
		return (0);
	int dir = dir_check(left, right);
	if (dir == 3)
		if (pipe[right.first - 1][right.second] || pipe[right.first][right.second - 1])
			return (0);
	if (right.first == N - 1 && right.second == N - 1)
		return (1);
	std::pair<int, int> dfs_left, dfs_right;
	std::vector<std::pair<int, int> > dir_right = g_right_dir[dir_distribute_right(dir)];
	std::pair<int, int> dir_left = g_left_dir[dir_distribute_left(dir)];
	dfs_left.first = left.first + dir_left.first;
	dfs_left.second = left.second + dir_left.second;
	int rtn_val = 0;
	for (size_t i = 0 ; i < dir_right.size(); i++)
	{
		dfs_right.first = right.first + dir_right[i].first;
		dfs_right.second = right.second + dir_right[i].second;
		int dp_dir = dir_check(dfs_left, dfs_right);
		if (dp_dir == 1)
		{
			if (dp_right[right.first][right.second])
				rtn_val += dp_right[right.first][right.second];
			else
				rtn_val += (dp_right[right.first][right.second] = dfs(dfs_left, dfs_right));
		}
		else if (dp_dir == 2)
		{
			if (dp_down[right.first][right.second])
				rtn_val += dp_down[right.first][right.second];
			else
				rtn_val += (dp_down[right.first][right.second] = dfs(dfs_left, dfs_right));
		}
		else
		{
			if (dp_diagonal[right.first][right.second])
				rtn_val += dp_diagonal[right.first][right.second];
			else
				rtn_val += (dp_diagonal[right.first][right.second] = dfs(dfs_left, dfs_right));
		}
	}
	return (rtn_val);
}

void solve()
{
	std::cout << dfs({0,0},{0,1});
}

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