백준 10942 / C++

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

10942번: 팰린드롬?

 

[ 풀이 ] 

어떤 문자열이 팰린드롬이라면 양쪽으로 1개씩 옮겨가면서 조사해줄 수 있다.

즉, 이전 상태를 다시 활용할 수 있으므로 메모이제이션이 가능한 문제다. 

dp[i][j]:= 구간[i,j]가 팰린드롬이면 1, 아니면 0을 의미한다고 하자. 

이제 [i-1, j+1]로 이동한다면.. a[i-1]=a[j+1]이고 dp[i][j]=1일때만 dp[i-1][j+1]도 1이 된다.

비트연산으로 간단히 하면 dp[i-1][j+1]=dp[i][j] & (a[i-1]==a[j+1]) 라고 할 수 있다. 

팰린드롬 길이가 홀수라면 1개부터 시작해서 2개씩 붙여나가고, 

짝수라면 2개부터 시작해서 2개씩 붙여나가면 된다. 기저조건은 숫자가 2개이하일때 잘 처리해주면 된다. 

 

[ 코드 ]

 

#include <bits/stdc++.h>
using namespace std;
int n, m, s, e, a[2002], dp[2002][2002];
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    // 길이 1, 2인 팰린드롬 
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 1;
        dp[i][i + 1] = (a[i] == a[i + 1]);
    }
    // i는 감소하고 j는 증가하므로 갱신 순서에 주의 
    for (int i = n; i >= 1; i--) {
        for (int j = i; j <= n; j++) {
            dp[i - 1][j + 1] = dp[i][j] & (a[i - 1] == a[j + 1]);
        }
    }
    cin >> m;
    while (m--) {
        cin >> s >> e;
        cout << dp[s][e] << '\n';
    }
}