팰린드롬 ?

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)

이미 dp에 값이 저장되어있는지 확인. 또한 board[x]와 board[y]의 값이 같은지 확인.
x의 값이 y값 + 1 보다 크거나 같다는 것은 더이상 탐색할 것이 없다는 뜻이므로 1번을 통해 board[x]와 board[y]의 값이 같은 것은 확인이 되었으므로 dp[x][y]를 1로 바꾼 후 리턴
탐색할 것이 있다면 dfs를 조건문안에 넣음으로써 탐색 결과 안 쪽이 모두 팰린드롬이라면 현재 board[x]와 board[y]는 같으므로 dp[x][y] = 1로 바꿔주고 리턴
그렇지 않다면 dp[x][y] = 0으로 바꿔주고 리턴

(+ 추가) N의 크기는 2000 이므로 N^2은 4,000,000 입니다. dp배열은 N * N 이므로 해당 값들을 저장하고 사용하는 것은 홍준이가 질문할 때 마다 그 값이 팰린드롬인지 계산하는 시간복잡도인(2000 x 1,000,000) 보다 훨씬 빠릅니다.

Code

제출 날짜

2021/03/13

메모리

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);
}