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

문제 출처

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

 

풀이

저는 문제가 잘 풀리지 않으면 무작정 쓰면서 고민해보는 편입니다. 

특히 규칙을 찾는 문제에서는 더더욱 그렇습니다.

이 문제 또한 그런 방법으로 풀었습니다.

 

어떤 파티션을 앞에서 읽는 것과 뒤에서 읽는 것이 같은 경우 팰린드롬 파티션이라 합니다.

그리고 왼쪽 절반과 오른쪽 절반이 재귀적인 팰린드롬이거나 비어있는 경우 재귀적인 팰린드롬 파티션이라 합니다. 

 

이 문제는 어떤 수의 재귀적인 팰린드롬 파티션의 갯수를 찾는 문제입니다.

 

다이나믹 프로그래밍 알고리즘을 이용해서 푸는 문제였는데 1부터 현재 수를 2로 나눈 몫까지 각각의 재귀적인 팰린드롬 파티션의 갯수를 더해주면 현재 수를 알아낼 수 있었습니다.

 

이 때 각각의 재귀적인 팰린드롬 파티션의 갯수를 구하기 위해 매번 더한다면 시간초과가 날 것이기에 한 번 구한 값을 먼저 배열에 저장해두는 것입니다.

 

코드

small-j/Algorithm