[백준] 10942번 팰린드롬? C++ 문제풀이

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

10942번: 팰린드롬?

문제 풀이

맨 처음에 감을 잡지 못해서 알고리즘 분류를 봤더니 DP...?  그때부터 DP로 문제를 풀 방법을 계속 생각했던거 같다.

S == E 인 경우는 무조건 팰린드롬이다 .

그리고 S = i , E = j 일때 i번째 수와 j번째 수가 같고, i+1 ~ j-1까지의 수가 팰린드롬이라면 -> i ~ j 는 팰린드롬이다.

위와 같은 규칙을 세우고 코드를 작성했는데 시간초과...

ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);  를 추가하고 했더니 4%에서 틀렸습니다가 나왔다.

반례

2
1 1
1
1 2

이 경우 팰린드롬인데 내 답은 0을 뱉어내더라...

i번째 수와 j번째 수가 같은데, j == i+1이면 dp[j][i] = 1이 되게 코드를 작성했더니 정답이였다!

소스 코드

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

int su[2001] = { 0 };
int dp[2001][2001] = { 0 };

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

	int n, m;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> su[i];
		for (int j = 1; j <= i; j++) {
			if (su[j] == su[i]) {
				if (j == i || j == i - 1)
					dp[j][i] = 1;
				else {
					if (dp[j + 1][i - 1] == 1)
						dp[j][i] = 1;
					else
						dp[j][i] = 0;
				}
			}
			else {
				dp[j][i] = 0;
			}
		}
	}

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