백준(Baekjoon)문제 풀이 - 10942 팰린드롬?(C++)

 팰린드롬?

문제

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

주어진 배열의 (s, e)구간이 팰린드롬인지 판단하는 프로그램을 작성하는 문제.

입출력 형식

<입력>

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

<출력>

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

 

<입력 예제>

7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7

<출력 예제>

1
0
1
1

아이디어

문제의 질문 수의 수의 최대값이  1,000,000임으로, 미리 어떤구간이 팰린드롬인지를 구해두고, 질문에대한 답을 출력해야함을 알 수 있다. n범위가 2000이하임으로, O(N^2)의 풀이까지 생각해 볼 수 있다. 우선, x, y가 팰린드롬인지에 관한 테으블을 채운뒤 규칙을 살피는 편이 좋을 것 같기에 테이블을 채워보자.

table[i][j] = i번째 문자열부터 j번째 문자열이 팰린드롬이라면 1 아니라면 0

1	0	1	0	0	0	1
	1	0	0	0	1	0
		1	0	1	0	0
			1	0	0	0
				1	0	1
					1	0
						1

<table>은 다음과 같이 채울 수 있으며, 이 테이블에서 규칙을 찾을 수 있다.

table[i][i] 즉, 배열의 길이가 1이라면 문조건 팰린드롬이다.

또, table[i+1][j-1] 이 팰린드롬이고, 주어진 배열 S[i] == s[j]라면 table[i][j] 또한 팰린드롬이라는 점이다.

즉, 1 2 1과같은 팰린드롬에 앞과 뒤에 같은 수가 추가된 배열이 있다면 그 배열 또한 팰린드롬이라는 소리이다.

여기까지왔다면 슬슬 이문제는 DP문제라는 생각을 할 수 있으며, 위에서 발견한 규칙들로 점화식을 세울 수 있다!

>점화식<

if (arr[i] == arr[j] && dp[i + 1][j - 1] == 1) dp[i][j] = 1;

하지만 이를 이용하여 코딩을 한다면, 몇가지 예외가 존재한다.

3
1 1 1
1
1 2

과 같은 데이터의 경우 1이 아닌 0이 나오는것이다. 즉, dp[i][i+1]또한 처리를 해주어야한다.

모두 처리하면 AC를 맞을 수 있다.

소스코드

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, m;
int arr[2010];
int dp[2010][2010];

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) scanf("%d", &arr[i]);
	for (i = 1; i <= n; i++) dp[i][i] = 1;
	for (i = 1; i < n; i++) if (arr[i] == arr[i + 1]) dp[i][i + 1] = 1;
	for (i = n; i >= 1; i--) {
		for (j = i + 1; j <= n; j++) {
			if (arr[i] == arr[j] && dp[i + 1][j - 1] == 1) dp[i][j] = 1;
		}
	}
	scanf("%d", &m);
	for (i = 0; i < m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		printf("%d\n", dp[x][y]);
	}
	return 0;
}