백준 10942 팰린드롬?

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

10942번: 팰린드롬?

 

 

 

EXPLANATION

 

 

수열이 팰린드롬이려면,

양끝이 같고 그 사이가 팰린드롬이면 된다.

 

 

수열의 길이가 1일 때는 숫자 하나 그 자체로 양끝이나 그 사이가 존재하지 않고,

수열의 길이가 2일 때는 양끝이 존재하지만, 그 사이가 존재하지 않는다.

따라서, 따로 미리 설정을 해야한다. (base)

수열의 길이가 1일 때는 그 자체로 팰린드롬이다.

수열의 길이가 2일 때는 2 숫자가 같으면 팰린드롬이다.

 

수열의 길이가 작은 거부터 확인해야,

이후에 더 큰 길이의 수열이 팰린드롬인 지 구할 때,

그 수열의 양끝 사이에 있는 수열을 이용할 수 있다.

for (int i = 2; i <= N - 1; i++) {	//수열의 길이 3부터 N까지. j~j+2: 3개, j~j+(N - 1): N개
    for (int j = 1; j <= N - i; j++) {	//j+i의 최대는 N.
    
    	//앞 뒤 사이에 있는 수들이 팰린드롬이면 팰린드롬.
        if (arr[j] == arr[j + i] && palindrom[j + 1][j + i - 1] == true) {
            palindrom[j][j + i] = true;
        }
    }
}

 

 

혹은,

for (int i = N - 2; i >= 1; i--) {
    for (int j = i + 2; j <= N; j++) {
        if (arr[i] == arr[j] && palindrom[i + 1][j - 1] == true) {
            palindrom[i][j] = true;
        }
    }
}

이렇게 해도 된다.

 

예를 들어 설명하겠다.

1 2 1 3 1 2 1

위와 같은 수열이 이루어졌을 때, 팰린드롬을 이루는 경우를 표로 나타내보자.

palindrom이 true면 O, false면 X.

테스트 케이스		1	2	1	3	1	2	1
palindrom		[1]	[2]	[3]	[4]	[5]	[6]	[7]
[1]		O	X	O	X	X	X	O
[2]			O	X	X	X	O	X
[3]				O	X	O	X	X
[4]					O	X	X	X
[5]						O	X	O
[6]							O	X
[7]								O

이렇게 보면 어디서부터 DP를 시작해야 할지 볼 수 있다.

if (arr[i] == arr[j] && palindrom[i + 1][j - 1] == true) palindrom[i][j] = true;이므로,

palindrom[s][e]를 확인하려면, palindrom[s + 1][e -1]을 알아야 한다.

그러면 dp는 가장 밑에서 부터 위로, 왼쪽에서부터 오른쪽으로 채워져야 한다.

그런데, 길이가 1, 2일 때인 palindrom[i][i], palindrom[i][i+1]은 이미 확인했으므로,

i= N - 2부터 1까지 1칸씩 내려오면 되고,

j = i+2부터 N까지 1칸씩 오른쪽으로 가면딘다.

그걸 표현한 것이 위의 2번째 코드.

 

 

 

 

 

CODE

#include <iostream>
using namespace std;

int arr[2001];
bool palindrom[2001][2001] = { false };

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

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

    	//길이가 1일 때는 무조건 팰린드롬.
    	palindrom[i][i] = true;

    	//길이가 2일 때, 2 수가 같으면 팰린드롬.
    	if (arr[i-1] == arr[i])
    		palindrom[i-1][i] = true;
    }


    //길이가 3이상 일 때, 앞 뒤가 같고, 앞 뒤 사이에 있는 수들이 팰린드롬이면 팰린드롬.
    for (int i = N - 2; i >= 1; i--) {
        for (int j = i + 2; j <= N; j++) {
            if (arr[i] == arr[j] && palindrom[i + 1][j - 1] == true) {
                palindrom[i][j] = true;
            }
        }
    }

    int M, S, E;
    cin >> M;

    for (int i = 0; i < M; i++) {
    	cin >> S >> E;
    	cout << palindrom[S][E] << '\n';
    }

    return 0;
}