팰린드롬? Gold 3
문제
접근법
2,000개의 수가 있는 수열의 s 위치부터 e 위치까지의 수열이 팰린드롬인지 확인하여 팰린드롬일 경우 1을 아닐 경우 0을 출력해야 합니다. 단, 팰린드롬에 대한 질의는 최대 1,000,000개입니다. 그래서 매 질의를 받을 때마다 새롭게 팰린드롬 유무를 판단할 경우 시간 내에 계산이 어렵습니다. 한번 계산한 질의에 대해서는 저장해 두고 저장한 결괏값을 최대한 활용하는 동적 계획법을 활용하여 이번 문제를 풀어야 합니다.
점화식은 다음과 같습니다. 점화식을 세우기 위해서 다음의 특징을 활용합니다. "임의의 위치 s에서 e까지의 수가 팰린드롬인지 판별할때 s위치의 값과, e위치의 값이 같고, 사이의 수열이 팰린드롬이라면 임의의 위치 s에서 e까지의 수는 팰린드롬이다."
\[ f(s, e)= \begin{cases}
(s = e), & true \\
(e - s = 1), & a[s] = a[e] \\
(otherwise), & a[s] = a[e] & \mbox{and}& f(s+1, e-1)
\end{cases} \]
전체 소스 코드
#include <iostream>
#define endl '\n'
int dp[2000][2000]{};
int arr[2000]{};
bool IsPalin(int s, int e)
{
// 계산한적 있다면
if (dp[s][e] != -1)
return dp[s][e];
// s와 e가 동일한 경우
if (s == e)
return dp[s][e] = 1;
// e가 s의 바로 옆 수일 경우. 두 수는 같아야 팰린드롬
else if (e - s == 1 && arr[s] == arr[e])
return dp[s][e] = 1;
// s와 e가 두 칸 이상 떨어져있는 경우. 서로 같고 s와 e 사이가 팰린드롬일경우 s e도 팰린드롬
else if (arr[s] == arr[e] && IsPalin(s + 1, e - 1) == 1)
return dp[s][e] = 1;
else return dp[s][e] = 0;
}
int main()
{
//입출력 성능향상을 위한 설정
std::ios_base::sync_with_stdio(false);
std::cout.tie(NULL);
std::cin.tie(NULL);
std::fill(&dp[0][0], &dp[1999][2000], -1);
int N; // N (1 ≤ N ≤ 2,000)
std::cin >> N;
for (int i = 0; i < N; ++i)
{
std::cin >> arr[i];
}
int M; // M (1 ≤ M ≤ 1,000,000)
std::cin >> M;
while (M--)
{
int s, e;
std::cin >> s >> e;
std::cout << IsPalin(s - 1, e - 1) << '\n';
}
return 0;
}
실행 결과