[백준-10943] 팰린드롬?

( "팰린드롬 "이란 뒤집어도 똑같은 수를 의미한다. )

일단 시간 제한이 0.5초(5천만줄) 정도이고, 입력의 크기가 2000 개의 수열의 크기, 백만개의 질문의 개수이다. 이를 보아 질문마다 2000 번의 연산을 하게 된다면 문제가 바로 터진다는 걸 알 수 있다.

때문에 백만개의 질문마다 log(n) 의 연산을 하던가 아예 처음에 다 계산한 이후 O(1) 의 복잡도로 답을 내버리던가 해야 한다.

 

팰린드롬은 대표적인 dp 문제라고 할 수 있다. 예를 들어

1, 2, 1, 3, 1, 2, 1

위와 같이 7개의 수가 있을 때 (3, 7) 이 팰린드롬인지 확인해보자.

(3,7) 은 1, 3, 1, 2, 1 로 양끝의 수가 같은 팰린드롬 같은(?) 수이다. 이 때 양끝의 수가 같으니 (3, 7) = (4, 6) 이라는 걸 유추할 수 있다. 이 상태 관계를 가지고 Dynamic Programming 을 해줄 수 있다.

즉, (a,b) 는 a번째 수와 b 번째 수가 같다면 (a,b) = (a+1, b-1) 이 되고, 당연히 같지 않다면 (a,b) = 0 이 된다.

#include <iostream>

using namespace std;

int arr[2001];
int dp[2001][2001];

void initialize() {
	for (int i = 0; i < n; i++) {
		for (int j =1; j <= n - i; j++) {
			if (i == 0) {
				dp[j][j + i] = 1;
			}
			else if (i == 1) {
				dp[j][j + i] = (arr[j] == arr[j + i]) ? 1 : 0;
			}
			else {
				if (arr[j] == arr[j + i]) 
					dp[j][j + i] = dp[j + 1][j + i - 1];
				else 
					dp[j][j + i] = 0;
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, m, a, b;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i];

	// initialize dp arr
	initialize();

	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		cout << dp[a][b] << "\n";
	}
	
	return 0;
}

 

https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?