[백준] 10942 팰린드롬?

팰린드롬

팰린드롬(Palindrome)은 회문자라고도 하며 앞으로 읽으나 뒤로 읽으나 같은 내용이 되는 문자나 문장을 말한다.

기러기 토마토 스위스 인도인 별똥별 우영우! 이거를 찾는 것이다

Problem

아주 아주 어렵다 정답률은 29%이고, 이는 시간초과 이슈때문인 것으로 보인다..
시간초과는 DP를 활용하여 해결하였는데, DP의 Top-up방식의 배열을 채울 수 있는 순서대로 채워서 푸는 것이 중요한 문제다. 여기서 배열을 채워넣을 때 핵심아이디어를 생각해내는 것이 중요 issue이다..!

첫번째 풀이

애초에 구현하기 전에 시간초과부터 계산해보는 습관을 들여야 한다.

#include<iostream>
using namespace std;
int N, M;
int num[2000];
bool Palindrome(int s, int e) {
	int size = e - s + 1;
	if (size == 1) return true;
	for (int i = s; i <= s + size / 2; i++) {
		if (num[i] != num[e - i]) {
			return false;
		}
	}
	return true;
}

int main() {
	//freopen("input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		if (Palindrome(s - 1, e - 1)) {
			cout << 1 << "\n";
		}
		else {
			cout << 0 << "\n";
		}
	}
}

이것의 시간초과 이슈는

for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		if (Palindrome(s - 1, e - 1)) {
			cout << 1 << "\n";
		}
		else {
			cout << 0 << "\n";
		}
	}

다음의 코드에서 M이 1,000,000이고, Palindrome함수에서 최대 2000까지 커질 수 있으므로 1,000,000 * 2,000로 시간초과가 발생할 수 있다는 점을 인지하고, 다른 풀이를 생각했어야 한다.

두번째 풀이

도저히 생각이 나지 않아서 힌트를 얻어 문제를 풀었다 문제를 생각하는 방식은 다음과 같다.

• dp[s][e] 가 팰린드롬인지 아닌지 미리 정해두자
• 초기화
  dp[s][s] 인 경우는 모두 팰린드롬 => dp[s][s] = 1
  저장해둔 배열의 num[s] == num[s + 1]이면 dp[s][s + 1]이 팰린드롬 =>dp[s][s + 1] = 1
• point

1. 1234567654321에서 23456765432이 부분이 팰린드롬이고, 동시에 맨처음과 끝이 동일하다면 팰린드롬 아닌가?
2. 천천히 쌓아 나가야 함 How?
   크기가 3인 것부터 크기별로 확인을 해봐야 한다.

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

• 만약 그냥 dp의 (0,0)부터 (N-1,N-1)의 순서대로 확인한다면 놓치는 것이 발생할 것이다. 당연하다 만약 num배열에 9글자짜리 팰린드롬수가 있는데 한번만으로는 3글자만 팰린드롬수로 체크할 수 밖에 없기 때문이다.

• 이 문제가 DP 문제인 이유는 팰린드롬수의 크기의 내림차순으로 팰린드롬수와 아닌 수를 구분하며 배열을 채워나가기 때문이다..!

• 1자리 팰린드롬 -> 2자리 팰린드롬 -> 3자리 팰린드롬인것 찾기... 순서대로

for (int size = 2; size < N; size++) { // size가 3인 것부터 확인하면서 팰린드롬수의 범위인것 찾아내기
		for (int i = 0; i < N - size; i++) {
			if (dp[i + 1][i + size - 1] && num[i] == num[i + size]) dp[i][i + size] = 1;
		}
	}