[백준][10942번][DP] 펠린드롬?

펠린드룸?

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

<코드>

#include <stdio.h>
int Dp[2001][2001] = {};
int main(void){
 
    int N;
    int room[2001] = {};
 
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%d", &room[i]);
 
    int questNum;
    scanf("%d", &questNum);
 
    for (int i = 1; i <= N; i++){
        Dp[1][i] = 1;
        Dp[0][i] = 1;
    }
    for (int i = 2; i <= N; i++){
        for (int j = 1; j <= N-i+1; j++){
            if (room[j] == room[j + i - 1] && Dp[i - 2][j + 1] == 1)
                Dp[i][j] = 1;
        }
    }
    while (questNum--){
        int S, E;
        scanf("%d %d", &S, &E);
        printf("%d\n", Dp[E-S+1][S]);
    }
}

<문제 푼 요령>

1. DP 문제면 보통 먼저 체크를 해놓고 그 체크해놓는걸 어떻게 사용하느냐가 문제인데 여기서는 생각하기가 쉽지 않았다.

2. 그래서 구분을 하는 방법을 만약 i에서 시작해서 j 까지 숫자로 펠린드 룸을 만들 수 있다고 가정을 하면 일단 room[i] == room[i+j-1] 은 같아야 한다. 그리고 이전에 저장한 것을 이용하여서 Dp[i-2][j+1] 이 이미 펠린드 룸이여야 한다. 

3. 위 방식대로 진행하면 모든 펠린드 룸이 체크된다.