백준 10942 - 팰린드롬?(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

Dp를 이용한 문제입니다.

자연수 N개와 질문 M개가 주어졌을 때, 질문이 옳은지를 구하는 문제입니다.

 

 

펠린드롬은 수열의 중간을 기준으로 양옆이 같은 것입니다.

 

그렇다면 간단하게 얻을 수 있는 값들이 있습니다.

1. 자기 자신만을 범위로 가지면 무조건 펠린드롬이다.

2. 길이가 2일 경우에는 옆만 확인해보면 된다.

-> 2개의 경우는 값을 쉽게 얻을 수 있습니다.

 

그렇다면 3개 이상부터는 어떻게 구해야할까요?

예를 들어, 1 2 1 이라는 수가 있다고 해보겠습니다.

해당 수를 펠린드롬이라고 구하는 방법은 

1. 양 끝값이 같은지?

2. 양 끝값을 제외한 값이 펠린드롬을 이루는지?

해당 2가지만 맞으면 수가 펠린드롬인지를 구할 수 있습니다.

 

따라서 1 2 1인 경우 양 끝 값이 1로 같고, 양 끝은 제외한 수인 2가 펠린드롬이기에 펠린드롬이라고 할 수 있습니다.

 

1 3 3 1인 경우, 양 끝 값이 같고, 양 끝 값을 제외한 값이 3 3 이기에 해당 수는 펠린드롬이라고 할 수 있습니다.

 

이와 같은 방법으로 구하면 펠린드롬인지 구할 수 있습니다.

 

저는 dp[x][y] 라는 배열을 만들었고, 이는 X~Y가 펠린드롬이면 1, 아니면 0으로 저장했습니다.

해당 배열의 값을 이용한다면 쉽게 문제를 풀 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#define P pair<int,int>
#define F first
#define S second
#define LL long long

using namespace std;

int N, M;
int map[2001];
int dp[2001][2001];
vector<P> ques;

void solve(){
    for(int i = 1; i <= N; i++){
        dp[i][i] = 1;   
    }
    for(int i = 1; i < N; i++){
        if(map[i] == map[i+1]) dp[i][i+1] = 1;
    }
    for(int i = N-1; i >= 1; i--){
        for(int j = i+2; j <= N; j++){
            if(dp[i+1][j-1] == 1 && map[i] == map[j]) dp[i][j] = 1;
        }
    }
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; i++){
	    cin >> map[i];
	}
	solve();
	cin >> M;
	for(int i = 1; i <= M; i++){
	    int x, y;
	    scanf("%d %d", &x, &y);
	    cout << dp[x][y] << "\n";
	}
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요