[백준(BOJ)] 10942번 : 팰린드롬? C++ 풀이(DP)

문제:

접근:

그냥 하나씩 접근해서 비교하여 푸는 방식으로 하면, 시간내로 풀지 못한다.

따라서 점화식을 이용해서 풀면 된다.

즉, DP로 풀면 시간내로 풀린다.

 

전략:

시간을 최소로 사용해야하기 때문에 데이터를 메모라이징하여서 저장한다.

점화식은 구간 [i,j] 가 있을때, i==j(구간길이 1)이면 true, 구간길이가 2일때, 입력데이터 input[i] == input[j] 가 같으면 true 아니면 false로 저장하고, 나머지 구간은 dp[i,j] = dp[i+1, j-1]  && input[i] == input[j] 이면 된다.

(이전 데이터를 이용해서, 양옆 한번만 비교하면 된다.)

 

코드:

#include <iostream>
#include <vector>
using namespace std;

int n,m;
vector<int> su;
bool dp[2001][2001];

void make(){

    for(int i=0;i<=n;i++){
        for(int j=0;j <= n-i;j++){
            int row = j;
            int col = i + j;
            if(row == col) dp[row][col] = true;
            else if(row + 1 > col - 1){ 
                if(su[row] == su[col]) dp[row][col] = true;
            }else{
                dp[row][col] = dp[row+1][col-1] && (su[row] == su[col]);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;su.resize(n+1);
    for(int i=1;i<=n;i++){  
        cin >> su[i];
    }

    make();

    cin >> m;

    for(int i=0;i<m;i++){
        int start, end;
        cin >> start >> end;
        cout << dp[start][end] << '\n';
    }

    return 0;
}