BOJ 10942 팰린드롬? / C++

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

10942번: 팰린드롬?

백준 온라인저지 10942번 팰린드롬 문제입니다.

 

알고리즘

dp 문제입니다. 팰린드롬이란 앞에서 부터 읽어도, 뒤에서 부터 읽어도 같은 숫자 문자열 등을 의미합니다.

보진 않았지만 최근 이상한 변호사 우영우에서 나온대사 처럼 기러기, 토마토, 스위스, 인도인, 별똥별 .. 우영우 와 같은 단어들이 팰린드롬의 예시가 될 수 있습니다.

dp 테이블을 두고 E에서 S까지가 팰린드롬이면 dp[E][S]를 true로 기록하고 미리 만들어둔 dp 테이블로 테스트 케이스마다 팰린드롬인지를 판단했습니다. dp테이블은 문자열의 크기가 1, 2, 3이상 으로 나누어 접근했습니다.

1은 반드시 팰린드롬이고 2는 앞뒤가 동일한 숫자라면 팰린드롬입니다. 그리고 3이상일때는 if (arr[j] == arr[i + j] && dp[j + 1][i + j - 1]) 식을 만족해야 합니다. 예를 들어 2~5까지의 문자열을 판단한다고 할때 3~4까지의 문자열이 팰린드롬인지 확인하고 2와 5가 같다면 팰린드롬이 될수밖에 없죠. 이 식을 바탕으로 문자열의 길이만큼 확장해나간다면 dp 테이블을 완성할 수 있습니다.

 

#include <iostream>
#include <vector>

using namespace std;

int N, M, E, S;

vector<int> arr;
vector<vector<bool>> dp;

void solution() {
	cin >> N;
	arr.resize(N+1);
	dp.resize(N + 1, vector<bool>(N + 1, false));
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

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

	}
	for (int i = 2; i < N; i++) { //길이가 3이상일때
		for (int j = 1; j <= N - i; j++) {
			// 배열의 앞뒤가 같고 앞뒤 사이에 있는 수가 팰린드 수 일때
			if (arr[j] == arr[i + j] && dp[j + 1][i + j - 1]) 
				dp[j][i + j] = true;
		}
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> E >> S;
		cout << dp[E][S] << "\n";
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
}
//https://www.acmicpc.net/problem/10942