[BAEKJOON] 10942번 : 팰린드롬?

문 제

 

소 스  코 드

#include <iostream>

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

	int N, M;
	std::cin >> N;

	int *arr{ new int[N] };
	int **dp{ new int*[N] };
	for (int i = 0; i < N; ++i) std::cin >> arr[i];
	for (int i = 0; i < N; ++i) {
		dp[i] = new int[N];
		std::fill_n(dp[i], N, -1);
	}


	for (int i = 0; i < N; ++i) dp[i][i] = 1;

	for (int i = 1; i < N; ++i) {
		for(int j = i; j < N; ++j) {
			if ((arr[j - i] == arr[j]) && (dp[j - i + 1][j - 1])) {
				dp[j - i][j] = 1;
			}
			else dp[j - i][j] = 0;
		}
	}

	std::cin >> M;
	int start, end;
	for (int i = 0; i < M; ++i) {
		std::cin >> start >> end;
		std::cout << dp[start - 1][end - 1]<< '\n';
	}


	for (int i = 0; i < N; ++i) delete[] dp[i];
	delete[] dp;
	delete[] arr;
	

	return 0;
}

 

풀 이

 

• 회문, 팰린드롬(Palindrome) 이란?

질문의 S와 E가 존재할 때 Mid를 기준으로 비교하는 것은 반복을 통해 많은 시간을 필요로 한다.

그러므로 미리 dp를 통하여 그 범위가 회문인지를 확인하고 저장하여 실행시킨다.

배열의 크기는 최대 2'000 * 2'000 이다.

 

위의 과정을 통하여 값을 구하려고 한다.

1. S와 E가 같을 경우에는 회문이 맞다.

2. 만약, 

 

A == D가 같고, B C D가 회문이 맞다면 A ~ D 까지는 회문이다.
B == E가 같고, C D가 회문이 맞다면 B ~ E 까지는 회문이다.

 

3. S와 E의 차이가 i일 경우, j에 대하여 ( j - i  ) ~ j 가 각 차이의 범위 이다.
   범위를 구할 경우, i의 범위는 1 ~ ( N - 1 )이다. 이때 이미 구해진 2칸 전의 범위 확인을 통하여 
   값을 찾을 수 있다.

   if ( arr[ j - i ] == arr[ j ] && dp[ j - i + 1 ] [ j - 1 ] )

 

 

 

 

출 력 값

 

 

문 제  출 처

문제 링크 : https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?