반응형
SMALL
팰린드룸 파티션
-
2705번 팰린드룸 파티션알고리즘 2023. 1. 24. 09:16
문제 설명 이번 문제는 1+2+1+7+1+2+1과 같이 읽을 때 재귀적으로 왼쪽 절반과 오른쪽 절반이 같은 재귀적인 팰린드룸 파티션의 개수를 출력하는 문제입니다. 7의 재귀적 팰린드룸 7 1+5+1 2+3+2 1+1+3+1+1 1+1+1+1+1+1+1+1 문제 풀이 아이디어 dp 양의 정수 N을 양의 정수의 합으로 나타낸다는 것에 초점을 맞춰보겠습니다. N을 임의의 수 a+b+a라는 숫자로 나타냈을 경우(N>=b>=0, N/2>=a>0) 이는 재귀적인 팰린드룸이 됩니다. 여기서, 양쪽 a를 또 재귀적인 팰린드룸으로 나타낸다면 이 또한 재귀적인 팰린드룸이 됩니다. 이와 같은 풀이는 피보나치 수열과 같이 이전의 결과값을 저장하고 현재 값을 계산할 경우 이전의 결과값을 사용하는 dynamic programmi..