백준[10942] - 팰린드롬?

문제

백준 10942 문제 보기

접근 방법

질문의 갯수가 최대 1000000이고 배열을 부분적으로 검사까지 진행해야하니 이는 다이나믹으로 해결해야한다. 일단 팰린드롬은 숫자가 범위 구간내에 대칭이 이루어져야 하므로 이 점을 고려해 점화식을 세워야한다.

• bottom-up 방식으로 먼저 길이가 1일 경우는 모두 팰린드롬이므로 dp[i][i] = 1을 저장한다.
• 길이가 2일 경우는 두개의 값이 일치할 경우 dp[i][j] = 1을 저장한다.
• 길이가 3이상일 경우는 i에서 부터 j까지라면 i+1, j-1은 팰린드롬이고 arr[i] == arr[j]를 만족할 경우 dp[i][j] = 1을 저장하는 식을 해결했다.

코드

#include <iostream>

using namespace std;

int N, M;
int dp[2001][2001];
int arr[2001];

int main() {
    cin >> N;

    for(int i = 1; i <= N; i ++)
        scanf("%d", &arr[i]);

    // 길이가 1
    for(int i = 1; i <= N; i ++)
        dp[i][i] = 1;

    // 길이가 2
    for(int i = 1; i <= N-1; i ++) {
        if(arr[i] == arr[i+1])
            dp[i][i+1] = 1;
    }

    // 길이가 3이상
    for(int k = 3; k <= N; k ++) {
        for(int i = 1; i <= N-k+1; i ++) {
            int j = i+k-1;
            if(arr[i] == arr[j] && dp[i+1][j-1] == 1)
                dp[i][j] = 1;
        }
    }

    cin >> M;
    for(int i = 0; i < M; i ++) {
        int from, to;
        scanf("%d %d", &from, &to);
        printf("%d\n", dp[from][to] );
    }
    return 0;
}