[백준 10942] 팰린드롬?

문제 링크 => 10942번: 팰린드롬? (acmicpc.net)

10942번: 팰린드롬?

 

다이나믹 프로그래밍 문제이다.

 

문제가 약간 이상한 느낌인게 칠판에 적는 숫자가 항상 1의 자리 숫자인 것 같다.

 

예를 들어서 1, 23, 232, 1, 232, 32, 1 에 대한 palindrome 처리를 할 때 [2, 3] 에 대한 Query 는 true 가

나와야 함에도 불구하고 통과한 코드는 false 처리를 한다는 것이다.

 

그래서 모든 input 을 1의 자리로 생각하고 풀었더니 굉장히 간단해졌다.

 

Optimal Substructure 를 생각해보면 다음과 같은 점화식이 나온다는 것을 알 수 있다.

 

P(x, y) = x 번째 부터 y 번째까지의 숫자가 palindrome 이면 1, 아니면 0

A[i] = 칠판에 적힌 숫자 라고 할 때,

 

(1) P(i, i) = 1 

 

(2) P(i, i + 1) = (A[i] == A[i + 1] ? 1 : 0)

    

(3) P(i, j) = (P(i + 1, j - 1) == 1 and A[i] == A[j] ? 1 : 0)    // j - i > 1 

 

여기서 (1), (2) 는 1의 자리 숫자임을 고려한다면 당연한 결과다.

 

그러나 (3) 에 대한 index 접근에 대해서 생각을 할 필요가 있다.

 

먼저 P(i, j) 는 [i + 1, j - 1] 범위에 대하여 반드시 palindrome 여야만 하고,

그 후에 A[i], A[j] 까지 동일해야만 [i, j] 범위에 대해서 palindrome 임을 짐작할 수 있다.

 

그러나 P(i, j) 를 구하기 위해서 P(i + 1, j - 1) 에 대한 정보가 반드시 필요하다. 

 

 

위 그림과 같이 대각선(왼쪽 + 아래) 에 위치한 정보가 필요하므로 index 접근을 다음과 같이 해야 한다.

 

 

for (int i = N - 2; i >  0; i--) {
    for (int j = i + 2; j <= N; j++) {
        // Palindrome operation...       
    }
}

 

그리고 시간 초과가 날 수 있으므로 endl 대신에 '\n' 을 꼭 해주자.

 

왜 endl이 '\n' 보다 시간이 오래걸리는지? 에 대해서는 나중에 시간날 때 공부해봐야 겠다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>

#define INF 1000000000

using namespace std;

int N, M;
int A[2001], P[2001][2001];

void Palindrome() 
{
	// set the table
	for (int i = 1; i <= N; i++) 
		P[i][i] = 1;
	for (int i = 1; i < N; i++)
		P[i][i + 1] = (A[i] == A[i + 1] ? 1 : 0);
	
	// dynamic programming
	for (int i = N - 2; i >  0; i--) {
		for (int j = i + 2; j <= N; j++) {
			if (P[i + 1][j - 1] && A[i] == A[j])
				P[i][j] = 1;
			else
				P[i][j] = 0;
		}
	}
}

int query(int S, int E) 
{
	return P[S][E];
}

int main(void) 
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}

	Palindrome();
	
	cin >> M;
	while (M--) {
		int S, E;
		cin >> S >> E;
		cout << query(S, E) << '\n';
	}

	return 0;
}