백준 10942 - 팰린드롬? (Python)

https://acmicpc.net/problem/10942 

10942번: 팰린드롬?

정말 오랫동안 괴롭힘당한 문제였다. 많은 풀이 방법을 시도해봤는데 전부 틀렸다.

dictionary로 캐싱을 시도하고 회문을 구하는 방법을 구하는 등 여러 방법을 시도했지만, 결과적으로 메모이제이션을 이용해야 했던 것은 맞으나 이중 리스트를 이용해 메모이제이션을 구현해야 했다.

a점부터 b점까지가 팰린드롬이면, 이중 리스트 dp[a][b]=1로 바꿔주는 것이 이 문제풀이의 핵심이다.

우선 확실하게 팰린드롬인 것들을 처리해준다. 한 글자짜리와 두 글자가 서로 같은 경우이다.

그 후, 모든 길이의 팰린드롬을 탐색해주는데, 이 때 확인해야 할 것은 내가 확인할 시작점~끝점 바로 안에 있는 숫자가 팰린드롬인지와 시작점과 끝점이 같은지이다. 이렇게 두 번씩만 확인하면 시간 내에 문제를 풀 수 있다.

​

그 외에도 하나 다시 알게 된 사실이 있었다.

pypy3에서 표준 입력을 받는 것이 오히려 느리다고 생각했었는데, 아니었다.

이렇게 정말 많은 양의 입력을 받을 때는 import를 해야 한다 해도 표준 입력을 사용하는 것이 낫다.