[코딩테스트] 백준 10942번: 팰린드롬?(다시 복습 완료,6/20)

-문제: https://www.acmicpc.net/problem/10942

문자열 뒤집어서 생각하면 되겠지라고 단순하게 여겼는데, 생각보다 어려웠던 문제. dp문제이니 dp원리로 푸는 연습 꾸준히 해야할 것 같다 

 

-참고한 블로그

[파이썬] 백준 10942. 팰린드롬?

 

 

이해한 원리로는

• start부터 end까지 팰린드롬인지 확인하려고 할 때, 문자열 start+1 부터 end-1까지 팰린드롬이라면 start와 end만 비교하면 팰린드롬인지 알 수 있다. 
• 즉, 어떤 문자열이 팰린드롬인지 확인하려면 양 끝의 문자가 같은지를 확인하고 양 끝단을 제외한 문자열이 팰린드롬인지 확인하면 된다

따라서, 어떤 문자열이 팰린드롬인지를 판단하는 과정은 다음과 같다.

• 양 끝의 문자가 다르면 -> 팰린드론 아님 
• 양끝의 문자가 같을 때, 가운데 문자열이

         -팰린드롬이라면 팰린드롬

         -팰린드롬이 아니라면 팰린드론 아님 

• 가운데 문자열이 팰린드롬인지 아닌지 모른다면 알 때까지 문자열의 길이를 앞뒤로 하나씩 줄이면서 위의 과정을 반복한다

-> 문자열의 범위를 줄여가면서 같은 과정을 계속 반복한다는 점에서 DP 문제라고 할 수 있다

           

 

-정답풀이: