문제접근
처음 생각으론 s와 e가 주어졌기 때문에 인덱스를 조정해가면서 비교를 하면 되지 않을까 생각을 했다.
하지만 우리 문제의 경우 여러 질문을 하게 되고 똑같은 과정을 계속 반복을 하게 되기 때문에 시간초과가 발생하게 된다.
따라서 dp를 통해서 계속 반복되는 부분에 대한 연산을 줄여야 한다.
우리는 반복된 연산을 줄이는 과정에 대해서 생각을 해야한다.
일단, 위와 같이 s와 e를 입력 받았을때 우리는 아래와 같은 검증 순서를 가지게 된다.
1.
s와 e가 같은지 확인
2.
s와 e사이가 팰린드롬인지 확인
따라서 우리는 2번의 과정에서 유리하게 쓸 dp를 하나하나 저장을 해나가면 된다
DP[s][e]의 형태는 s번째부터 e번째가 팰린드롬인지 아닌지 1 or 0으로 나타낸다고 할때, 길이 1인 녀셕들은 위와 같고 모두 1로 나타낼 수 있다.(DP[1][1] = 1 ...)
마찬가지로 길이가 2인 녀석들에 대해서도 값을 입력할 수 있다.
현재 위의 경우 서로 값이 같지 않기 때문에 모두 0으로 초기화가 될 것이다. (DP[1][2] = 0 ...)
길이가 3 이상인 경우부터에 대해서도 생각을 해보겠다.
예시로 길이가 4이면서, s = 1 e = 4인 경우로 예시를 확인해보자.
우리는 s와 e가 같은지를 확인한 다음, 그 사이의 숫자들이 팰린드롬을 이루는지 확인하게 된다.
물론, 위의 경우 s와 e가 이미 같지 않기 때문에 더 확인할 필요가 없지만 '같다'라고 가정을 하게 되면 우리는 파란 부분이 팰린드롬을 이루는지 확인을 해야한다.
이때, 우리는 파란부분은 길이가 2일때인 경우를 미리 구해뒀기 때문에 DP[2][3]을 그대로 가져와서 사용을 하면 된다.
//pseudo code
vector<int> input_arr
vector<vector<int> > dp
dp는 0으로 초기화
cin >> n;
while (i <= n) //길이가 1
dp[i][i] = 1;
while (i <= n - 1) //길이가 2
if(input_arr[i] == input_arr[i+1])
dp[i][i+1] = 1;
while (길이가 3이상부터 n까지) //길이가 3이상
while (n-k+1까지)
if (input_arr[i] == input_arr[j] && dp[i+1][j-1] == 1)
dp[i][j] = 1;
C++
복사
놓쳤던 부분
코드
17860 KB
228 ms
#include <iostream>
#include <vector>
int n;
std::vector<int> input_arr;
std::vector<std::vector<int> > dp;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
int i = 0;
std::cin >> n;
input_arr.resize(n + 1);
dp.resize(n + 1, std::vector<int>(n + 1, 0));
while (++i <= n)
std::cin >> input_arr[i];
}
void solution()
{
int i = 0;
int j, k;
while (++i <= n)
dp[i][i] = 1;
i = 0;
while (++i <= n - 1)
if (input_arr[i] == input_arr[i + 1])
dp[i][i + 1] = 1;
k = 2;
while (++k <= n)
{
i = 0;
while (++i <= n - k + 1)
{
j = i + k - 1;
if (input_arr[i] == input_arr[j] && dp[i + 1][j - 1] == 1)
dp[i][j] = 1;
}
}
}
void print()
{
int m;
int s,e;
std::cin >> m;
while (m--)
{
std::cin >> s >> e;
std::cout << dp[s][e] << "\n";
}
}
int main(void)
{
input_setting();
input();
solution();
print();
return (0);
}
C++
복사
