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

- 문제 구성 및 이해

 

팰린드롬: 121 처럼 뒤집어도 숫자가 같은 것을 지칭한다.

 

시간 제한이 0.5초, N <= 2000, 질문 수 <= 1000000 이므로 n * m 으로 풀 수없음 -> dp 활용

 

top -> bottom 방식의 dp를 활용

 

---

 

기본적인 점화식

dp[i][j] -> i와 j 가 펠린드롬인지 아닌지를 true, false로 나타내줌

 

---

 

1. dp[i][i] 는 true로 미리 적용; 한자리 수는 무조곤 펠린드롬 수

2. dp[i][j] 를 구하기 위한 방법 적용

    1) dp[i][j] == true -> 바로 true 반환 ( 함수 이용 )

    2) dp[i][j] == false && list[i] == list[j] (입력받은 배열) 면 재귀 호출을 이용하여 dp[i+1][j-1] 값으로 이동 

3. 함수의 반환값이 dp[i][j] = 재귀함수(dp[i+1][j-1]) 이므로 값 저장 가능!

 

#include <iostream>
#include <vector>

std::vector<std::vector<bool>> dp;
std::vector<int> list;

bool check(int a, int b) {
	if (dp[a][b]) return true;
	else if (list[a] != list[b]) return false;

	if (a + 1 <= b - 1) {
		return dp[a][b] = check(a + 1, b - 1);
	}
	else return true;
}

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n;
	std::cin >> n;

	list.assign(n + 1, 0);
	dp.assign(n + 1, std::vector<bool>(n + 1, 0));

	for (int i{ 1 }; i <= n; i++) {
		std::cin >> list[i];
	}
	
	for (int i{ 1 }; i <= n; i++) {
		dp[i][i] = true;
	}

	int m;
	std::cin >> m;

	int a, b;
	for (int i{ 0 }; i < m; i++) {
		std::cin >> a >> b;

		std::cout << check(a, b) << "\n";
	}
}