[BOJ] 팰린드롬? - Compy's Blog

팰린드롬?

TimeLimit	MemoryLimit	Condition	TAG
0.5s	256MB	(1≤ N ≤ 2,000 1 ≤ M ≤ 1,000,000)	Dynamic Programming

일단 문제 자체가 최적화를 좀 해야된다는 생각을 만들게 하는 TimeLimit였다. 그런데 점화식 세우는게 어려운 문제가 아니였고, 사실 디게 직관적인 문제여서 금방 풀었던 것 같다.

문제의 경우 그냥 자기 자신, 그리고 바로 2개씩 묶을 때 가능한 친구들 전처리하고, 이후에 바로 다 미리 전부 얻어둔 후에 입력으로 dp array에서 바로 빼오면 되는 문제다.

정답 코드

#include <iostream>
using namespace std;

using ll = long long;
int n, m;


int board[2001];
bool dp[2001][2001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++) cin >> board[i];
    
    
    // 2개씩 미리 해놓고, 다음에 차차 bottom up으로 처리하면 자동으로 다 dp 처리됨.
    
    for(int i = 1; i < n; i++){
        dp[i-1][i] = board[i] == board[i-1];
        dp[i-1][i-1] = 1;
        dp[i][i] = 1;
    }
    
    for(int i = 2; i < n; i++){
        for(int j = 0; j < n-i; j++){
            if(board[j] != board[i+j]) continue;
            dp[j][j+i] = dp[j+1][j+i-1];
        }
    }
    
    
    cin >> m;
    int a, b;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        
        cout << (dp[a-1][b-1] || dp[b-1][a-1]) << "\n";
    }
    return 0;
}
// 1 2 1 3 1 2 1