c언어 10942 팰린드롬 (백준)

#include <stdio.h>

int arr[2001] = {}; //정수의 배열 
char ans[2001][2001] = {}; //팰린드롬인지 아닌지를 담는 배열 맞으면 2, 아니면 1 

int loop(int s, int e) { //팰린드롬 구하는 재귀함수 
	if(s==e) ans[s][e] = 2; //하나일 경우는 반드시 팰린드롬 
	if(ans[s][e]) return ans[s][e]; //이미 팰린드롬인지 아닌지를 dp로 저장했다면 바로 리턴 
	if(arr[s] != arr[e]) { //양 끝의 요소가 다르면 팰린드롬이 아니므로 
		ans[s][e] = 1; 
		return 1; //1 리턴 
	} else { //같다면 
		if(s+1 <= e-1) ans[s][e] = loop(s+1, e-1); //내부도 같은지를 검사 
		else { //만약 쭉 양쪽이 같았으며, 더 이상 남아있는 요소가 없다면 
			ans[s][e] = 2; //이는 팰린드롬이다. 
			return 2;	
		}
	}
}

int main(void) {
	int n, m;
	scanf("%d", &n);
	for(int i=1; i<=n; i++) scanf("%d", &arr[i]); //숫자 배열 입력 
	
	scanf("%d", &m);
	for(int i=0; i<m; i++) {
		int s, e; //s, e 입력
		scanf("%d %d", &s, &e);
		loop(s, e); //s부터 e까지의 정수 배열이 팰린드롬인지 확인 
		printf("%d\n", ans[s][e]>>1); //팰린드롬인지를 ans 배열에 넣었으므로, 이를 출력 
	}
}

 

풀이 : dp

 

1. 숫자들을 입력 받는다.

2. S E를 입력받는다.

3. S부터 E까지가 팰린드롬인지를 구해야 한다.

팰린드롬인지를 확인하려면, 가운데를 기준으로 수열이 대칭이어야 한다.

 

1 2 3 3 2 1 : 123    321 로 대칭이니 팰린드롬

1 2 1 : 가운데 2는 같으며 1 1 이 대칭이니 팰린드롬

 

즉 끝부터 가운데까지 양쪽의 요소가 같으면 팰린드롬임을 알아낼 수 있다.

그러나 S E 를 입력받고 팰린드롬을 구하고하는 과정은 한 번 하는데 시간이 많이 걸린다.

또한 같은 S E가 입력되면, 팰린드롬인지를 중복으로 구해야 한다. 이미 팰린드롬인지 알면서도 말이다.

 

그러기에 dp을 이용하여, 팰린드롬인지 아닌지가 확정된 얘들은 dp 에다 저장을 하면, 이미 구해져 있을 경우, 다시 팰린드롬을 구하려 시간을 낭비하지 않아도 된다.

또한 하나의 팰린드롬은 (길이가 3 이상인 경우) 끝 팰린드롬 끝   이렇게 볼 수 있다.

즉 팰린드롬인지를 확인 할 때, 길이가 3 이상이라면 자신 이외의 다른 수열의 팰린드롬의 유무도 확인 할 수 있다.

 

ex) 1 2 3 3 2 1

1    2 3 3 2    1 : 양쪽이 1로같다

1  2   33   2   1 : 양쪽이 2로같다

1  2  3   3  2  1 : 양쪽이 3으로 같다. 고로 팰린드롬이다.

 

즉 123321, 2332, 33는 팰린드롬이란 것을 알 수 있다.

 

이를 재귀함수와 dp로 구현 할 수 있다.

 

재귀함수 중에,

     값이 1개 라면 그 값을 return

     이미 dp에 값이 있다면, 그 값을 return

     양쪽 끝이 다르다면 팰린드롬이 아님을 return

     모든 요소를 비교해도 같다면, 팰린드롬이 맞음을 return 한다.

 

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

10942번: 팰린드롬?