Memo
•
많은 고민을 했는데(오래 걸렸습니다), 그 고민 끝에 나온 아이디어는 단 하나였습니다.
•
예를 들어, 30 20 10 20 30 이렇게 칠판에 적혀있다고 하면 만약 30에서 30의 팰린드롬을 구해 놓았다면 나중에 30 30 뿐만 아니라 20 20 도 팰린드롬이라는 것을 알 수 있습니다. 왜냐하면 30 30 이 팰린드롬이라면 그 사이는 무조건 팰린드롬이기 때문입니다.
•
따라서 dp를 2차원 배열로 선언합니다. S와 E를 받았을 경우를 예시로 dp의 의미를 설명하자면, dp[S][E]는 S와 E 사이가 팰린드롬인지를 나타냅니다. (dp 초기값은 -1로 정함. -1은 아직 팰린드롬 조사를 하지않음을 뜻함)
•
그 다음 dfs를 통해 dp[S + 1][E - 1] 를 조사합니다.
•
dfs의 초기 조건은 다음과 같습니다. (dfs 인자는 x, y)
1.
이미 dp에 값이 저장되어있는지 확인. 또한 board[x]와 board[y]의 값이 같은지 확인.
2.
x의 값이 y값 + 1 보다 크거나 같다는 것은 더이상 탐색할 것이 없다는 뜻이므로 1번을 통해 board[x]와 board[y]의 값이 같은 것은 확인이 되었으므로 dp[x][y]를 1로 바꾼 후 리턴
3.
탐색할 것이 있다면 dfs를 조건문안에 넣음으로써 탐색 결과 안 쪽이 모두 팰린드롬이라면 현재 board[x]와 board[y]는 같으므로 dp[x][y] = 1로 바꿔주고 리턴
4.
그렇지 않다면 dp[x][y] = 0으로 바꿔주고 리턴
(+ 추가) N의 크기는 2000 이므로 N^2은 4,000,000 입니다. dp배열은 N * N 이므로 해당 값들을 저장하고 사용하는 것은 홍준이가 질문할 때 마다 그 값이 팰린드롬인지 계산하는 시간복잡도인(2000 x 1,000,000) 보다 훨씬 빠릅니다.
Code
제출 날짜
@3/13/2021
메모리
17860 KB
시간
212 ms
#include <iostream>
#include <vector>
#define endl "\n"
int N, M, S, E;
std::vector<int> board;
std::vector<std::vector<int> > dp;
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 + 1);
dp.resize(N + 1, std::vector<int>(N + 1, -1));
for (size_t i = 1 ; i <= N ; i++)
std::cin >> board[i];
std::cin >> S;
}
bool dfs(int x, int y)
{
if (board[x] != board[y] || !dp[x][y])
dp[x][y] = 0;
else if (dp[x][y] == 1)
return (dp[x][y]);
else if (x >= y - 1)
dp[x][y] = 1
else
dp[x][y] = dfs(x + 1, y - 1);
return (dp[x][y]);
}
void solve()
{
int a, b;
while (S--)
{
std::cin >> a >> b;
if (dp[a][b] == -1)
dfs(a, b);
std::cout << dp[a][b] << endl;
}
}
int main()
{
input();
solve();
return (0);
}
C++
복사
