[동적계획법, 난이도 중상] 백준 10942번 팰린드롬?

시간 제한은 0.5초이고 데이터범위는 100만인 시간 제한이 매우 빡센 문제이다.

이 때문에 문제의 난이도 평가를 중상으로 할지 상으로 할지 고민했다.

 

본인은 동적계획법으로 이렇게 접근했다.

 

예)

문제 입력에서

수열의 크기 N=12

그리고 칠판에 적은 수를 1 2 2 1 2 1 2 2 1 2 2 2로 가정했을 때의 dp표이다.

홍준이가 한 질문 최대 100만개는 이 표를 참고하여 대답해줄 것이다.

행은 팰린드롬의 길이, 열은 홍준이가 칠판에 적은 숫자를 나열한 것이다.

이 표는 팰린드롬의 중심을 기준으로 했을 때 길이 별 팰린드롬 여부를 나타낸 것이다.

예를 들어 7행 5열에서 "o"로 표시되어 있는데

흥준이가 칠판에 적은 숫자들중 5번째인 "2"를 중심으로 했을 때 연속 수의 길이가 7인 숫자열은 팰린드롬에 해당한다.

라고 해석하면 된다.

 

아래 소스코드에서 주석으로 //1행설정

이라고 달아 놓은 것은 숫자 하나는 무조건 팰린드롬이므로 d[1][i]를 모두 true라고 해준것이고

//2행설정

이라고 달아 놓은 것은 짝수 행 같은 경우에는 중심 수 2개중 왼쪽을 중심으로 잡을 것이므로 현재 수=다음 수라면,

d[2][i]=true라고 해준 것이다.

 

DP 반복문은 3행부터이다.

여기서 홀수 행은 홀수 행끼리, 짝수 행은 짝수 행끼리 계산한다.

현재의 좌표 를 d[i][j]라고 했을 때 바로 두 번째 아래 행의 좌표인 d[i-2][j]가 true(팰린드롬에 해당)이면서

자신 길이 i의 양끝 수가 같다면 d[i][j] 역시 true가 되는 식으로 DP를 설계하면 문제를 풀 수 있다. 

 

어렵지 않은 소스코드이니 홀수/짝수 행 각각의 자세한 처리는 이를 참고하길 바란다.

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
bool d[2001][2001];
int row[2001];
int q[1000001][2];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin >> n;
	for (int i = 1; i < n+1; i++) { //1행설정
		cin >> row[i];
		d[1][i] = true;
	}
	for (int i = 1; i < n; i++) { //2행설정
		if (row[i] == row[i + 1]) d[2][i] = true;
	}
	cin >> m;
	for (int i = 1; i < m+1; i++) {
		cin >> q[i][0] >> q[i][1];
	}
	for (int i = 3; i < n + 1; i++) {
		if (i % 2 == 1) { //홀수행 dp
			for (int j = i / 2 + 1; j < n + 1 - i / 2; j++) {
				if (d[i - 2][j] == true && row[j - i / 2] == row[j + i / 2]) d[i][j] = true;
			}
		}
		else { //짝수행 dp
			for (int j = i / 2; j < n + 1 - i / 2; j++) {
				if (d[i - 2][j] == true && row[j + 1 - i / 2] == row[j + i / 2]) d[i][j] = true;
			}
		}
	}
	for (int i = 1; i < m + 1; i++) {
		int size = q[i][1] - q[i][0] + 1;
		if (d[size][(q[i][1] + q[i][0]) / 2]) cout << "1" << "\n";
		else cout << "0" << "\n";
	}
}