팰린드롬? (feat. 백준, 10942번)

팰린드롬?
https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int arr[2001];
bool dp[2001][2001];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, M;
	cin >> N;
	for (register int i = 1; i <= N; ++i)
		cin >> arr[i];
	for (register int i = 1; i <= N - 1; ++i)
		if (arr[i] == arr[i + 1])
			dp[i][i + 1] = true;
	for (int i = 1; i <= N; ++i)
		dp[i][i] = true;
	for (int i = N - 1; i >= 1; --i)
		for (int j = i + 2; j <= N; ++j)
			if (arr[i] == arr[j] && dp[i + 1][j - 1] == true)
				dp[i][j] = true;
	cin >> M;
	for (register int m = 0, s, e; m < M; ++m)
		cin >> s >> e, cout << dp[s][e] << "\n";
	return 0;
}
// *&)*@*

1. 팰린드롬은 1 2 1 / 1 2 2 1 / 3 9 8 9 3 과 같이 x[0] == x[n] / x[1] == x[n - 1] / x[2] == x[n - 2] 와 같은 형태를 의미합니다.
2. 반복문을 통해 위의 내용을 확인할 수도 있지만 문제의 제한사항인 시간 에 걸리게 됩니다.
3. 따라서 dp를 통해 위 내용을 누적해 나가고, 다음번 확인은 이전의 결과를 체크하는 형태로 구현하면 됩니다.