백준 - 10942번 : 팰린드롬? (C++)

풀이 방법 : DP

팰린드롬이 되는 경우들을 따져보면

1. 자기 자신(길이 1)
2. 길이가 2 이면서 앞 뒤가 같은 경우
3. 길이가 3 이상 (j - i >= 2)일 때 Nums[i] == Nums[j] 이면서 i + 1 부터 j - 1까지의 수열이 팰린드롬인 경우

그래서 처음에 입력을 받으면서 check[i][i]는 무조건 true로, 길이 두 개이면서 앞뒤 같은경우는 check[i-1][i] = true를 처리 해줬다.

이러면 길이가 1인 케이스와 2인 케이스는 이미 해결이 된 것이고
길이가 3 ~ N인 녀석들을 3번의 조건에 따라 처리해주면 된다.

#include <iostream>
#include <vector>

using namespace std;

bool check[2001][2001] = {};

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

	int N, M;
	cin >> N;

	vector<int> vecNums(N + 1);

	for (int i = 1; i <= N; ++i)
	{
		check[i][i] = true;
		cin >> vecNums[i];

		if (i > 1)
		{
			if (vecNums[i] == vecNums[i - 1])
				check[i - 1][i] = true;
		}
	}

	for (int i = 2; i < N; ++i)
	{
		int Start = 1;
		int End = Start + i;

		while (End <= N)
		{
			if (check[Start + 1][End - 1])
			{
				if (vecNums[Start] == vecNums[End])
					check[Start][End] = true;
			}

			++Start;
			++End;
		}
	}

	cin >> M;

	while (M > 0)
	{
		int Start, End;
		cin >> Start >> End;

		if (check[Start][End])
			cout << 1 << '\n';

		else
			cout << 0 << '\n';

		--M;
	}

}

입력되는 M의 최댓값이 1,000,000이므로 빠른 입출력이 필요하다. 그러므로 c++ 스타일의 입출력을 사용한다면 밑의 코드를 필수적으로 작성해서 동기화를 필수적으로 해제 해주고 개행하는 데에는 '\n'을 사용해주자.

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

흑흑 이거 제외한 코드는 작성하는데 30분 컷 했는데 저거 생각못해서 고민만 한 시간 더 하다가 M 최댓값 보고 설마 하면서 넣어봤더니 바로 맞더라...