[성실코딩 12일차] 백준 #10942 팰린드롬? / DP

문제는 쉬운데 정답률이 왜 낮은가 했더니 

c++ 표준 입출력에 대한 시간초과 때문이었음!

입출력 속도향상 방법

1. cin, cout -> scanf, printf 사용하기

2. endl -> \n(개행문자) 사용하기

3. cin, cout을 사용하고 싶다면, 아래 적용하기!  대신 scanf, printf, puts, getchar, putchar 등 c의 입출력 방식을 공용해서 사용하지 못함.

ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL):

문제풀이

방법1. 완전탐색 -> 처음에 생각한 방법. 당연히 시간 초과날 것 같음.

처음 주어지는 값은 S<E인데, S>E가 될 때까지 두 수가 같아진다면 그 수는 팰린드롬이다.

(수도코드)

while(arr[s] == arr[e] ) s++; e--;
if(s<e) return false; 
// s<e일 경우, 두 수가 다를 때 while에서 벗어난 것이기 때문에 팰린드롬이 아니다.

방법2. DP

1) S번째 수와 E번째 수가 가리키는 수의 길이가 1개, 2개일 경우에는 -> 그 숫자들이 모두 같을 때만 팰린드롬이 됨

2) S번째 수와 E번째 수가 가리키는 수의 길이가 3개일 경우에는 -> 첫 번째, 세 번째 숫자가 같으면 팰린드롬이 됨. (가운데 2는 신경쓰지 않아도 됨)

따라서 S번째 수와 E번째 수가 같을 경우, S+1번째 수와 E-1번째 수가 같은지 재귀로 호출하며 확인함. 

(탈출하는 방법은 S와 E가 3이하 차이날 때는 그 수가 동일한지 다른지에 따라 return 0,1을 해줌)

#include <stdio.h>
#include <vector>

using namespace std;

int num[2001];
int n; // num size
vector<vector<int>> DP;

int populateDP(int _s, int _e) {
	
	if (DP[_s][_e]!=-1) {
		return DP[_s][_e];
	}

	//탈출조건
	if (_e<_s+3) { 
		if (num[_s]==num[_e]) {
			return DP[_s][_e] = 1;
		}
		else {
			return DP[_s][_e] = 0;
		}
	}

	//재귀
	if (num[_s]!=num[_e]) {
		return DP[_s][_e] = 0;
	}
	else {
		return DP[_s][_e] = populateDP(_s + 1, _e - 1);
	}
}

int main() {

	int tc;
	//cin >> n;
	scanf("%d",&n);
	DP.assign(n+1,vector<int>(n+1,-1)); // arr[n][n] -1로 초기화
	for (int i = 1; i <= n;i++) {
		//cin >> num[i];
		scanf("%d",&num[i]);
	}
	//cin >> tc;
	scanf("%d",&tc);
	for (int j = 0; j < tc; j++) {
		int s, e;
		//cin >> s >> e;
		scanf("%d %d",&s,&e);
		//cout << populateDP(s, e) << endl;
		printf("%d\n",populateDP(s,e));
	}

	return 0;
}