팰린드롬?

www.acmicpc.net/problem/10942

10942번: 팰린드롬?

 

#include<iostream>
#include<vector>
#include<cstring>


using namespace std;

int check[2002][2002];
bool toggle = false;
int find(int *arr, int s, int f) {

	if (s == f) { return 1; }
	else {
	
		if (check[s][f] != -1) { return check[s][f]; }
		if (s + 1 == f && arr[s] == arr[f]) { return 1; }
		if (arr[s] != arr[f]) {
			return 0;
	}
	
	}
	 //메모이제이션
	return check[s][f] =find(arr,s + 1, f - 1);
}



int main() {
	cin.tie(NULL);  //시간초과 방지
	ios::sync_with_stdio(false); //시간초과 방지
	int n;
	cin >> n;
	int arr[2002];
	
	for (int i = 1; i <=n; i++) {
		cin>>arr[i];
	}
	memset(check, -1 ,sizeof(check) );
	int m;
	cin >> m;
	int s, f;
	vector<int> answer;
	for (int j = 1; j <= m; j++) {
		cin >> s;
		cin >> f;
		answer.push_back(find(arr, s, f));

}

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

 

어떤 알고리즘 왜 그 알고리즘을 썼는지?

- 다이나믹 프로그래밍을 사용, 다이나믹프로그래밍이라고 따로 언급이 없으면 잘 몰랐을것 같다. 

- 다이나믹 프로그래밍을 쓸 수 있는 것은 양쪽값이 다르면 바로 그전의 값도 다 0이 되기 때문에 작은 문제들을 해결하면 큰문제를 해결할 수 있기 때문이다. 

- 시작과 끝에서 중간으로 모아지는데 둘의 값이 같아야한다 0이면 바로 리턴하도록 만들었다. 

- Top Down 방식으로 풀었다. Top Down을 하면서도 저장할 수 있는것은 check에도 저장 가능