Memo
어려웠던 점
처음에 완전 탐색으로 풀었는데 시간 초과가 나서 dp로 바꿔 풀었습니다. dp로 풀기 위해서는 파이프가 총 3방향으로 놓일 수 있기 때문에 3차원 배열로 풀어야 한다는 사실을 인지하는 것 까지가 어려웠습니다 (저는 이차원 배열 3개로 . 또한 파이프가 두 칸을 차지하기 때문에 어디에 값을 저장해야 하는지에 대한 고민도 필요했습니다. 삼성 기출문제들은 그냥 막 구현하면 될 것 같지만 생각을 좀 더 해보면 당연한 규칙들이 나오기 때문에 좀 더 깊게 고민해야 하는 것 같습니다.
아쉬웠던 점
•
이차원 배열을 반복문으로 돌면서 dp를 이용할 수 있는데, 그래프를 통해 풀어서 그런지 시간이 상당히 많이 소요되었습니다.
•
dfs함수 내에서 코드가 가독성이 떨어졌습니다.
Code
제출 날짜
@3/1/2021
메모리
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);
}
C++
복사
