[BOJ] 2705 - 팰린드롬 파티션

문제 출처 [BOJ] 2705 - 팰린드롬 파티션 풀이 저는 문제가 잘 풀리지 않으면 무작정 쓰면서 고민해보는 편입니다. 특히 규칙을 찾는 문제에서는 더더욱 그렇습니다. 이 문제 또한 그런 방법으로 풀었습니다. 어떤 파티션을 앞에서 읽는 것과 뒤에서 읽는 것이 같은 경우 팰린드롬 파티션이라 합니다. 그리고 왼쪽 절반과 오른쪽 절반이 재귀적인 팰린드롬이거나 비어있는 경우 재귀적인 팰린드롬 파티션이라 합니다. 이 문제는 어떤 수의 재귀적인 팰린드롬 파티션의 갯수를 찾는 문제입니다. 다이나믹 프로그래밍 알고리즘을 이용해서 푸는 문제였는데 1부터 현재 수를 2로 나눈 몫까지 각각의 재귀적인 팰린드롬 파티션의 갯수를 더해주면 현재 수를 알아낼 수 있었습니다. 이 때 각각의 재귀적인 팰린드롬 파티션의 갯수를 구하기..