[백준/BOJ] 백준 10942번 : 팰린드롬?

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

10942번: 팰린드롬?

 

 

cache[s][e]에, s~e 범위가 팰린드롬인 경우 1, 아닌 경우 0을 저장하여 bottom up 방식으로 다이나믹 프로그래밍을 진행하여, DP 테이블을 채우고, 해당 값을 기반으로 질문에 대한 답을 구했다.

 

코드

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

int n, m;
int number[2005];
int cache[2005][2005]; //[s][e] = s~e 범위가 팰린드롬인 경우 1, 아닌경우 0
vector<int> output;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int input;
		cin >> input;
		number[i] = input;
	}

	for (int i = 1; i <= n; i++) {
		cache[i][i] = 1;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i - 1; j++) { //j~i가 팰린드롬이 되는지 확인한다
			//cache[min(i-1,j+1)][i-1] == 1 -> j~i에서 j 와 i를 제외한 값들이 팰린드롬이 되는지 확인
			//min(i-1,j+1)은, j+1한 값이 i-1보다 커지는것 방지 (ex j=1, i=2)
			if (number[j] == number[i] && cache[min(i - 1, j + 1)][i - 1] == 1) {
				cache[j][i] = 1;
			}
		}
	}

	cin >> m;
	for (int i = 0; i < m; i++) {
		int s, e;
		cin >> s >> e;

		output.push_back(cache[s][e]);
	}

	for (int i = 0; i < output.size(); i++) {
		cout << output[i] << "\n";
	}

	return 0;
}