2705번 팰린드룸 파티션

문제 설명

이번 문제는 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 programming과 같습니다.

 

풀이

위의 아이디어에서 dp를 이용하여 풀이하기로 했습니다.

dp배열에는 숫자 i의 재귀적인 팰린드룸 개수를 저장합니다.

우선 반복을 돌기 전에 초기 dp[0], dp[1]값만 넣어줍니다.

• dp[0] = 1
• dp[1] = 1

그 다음, 테스트 케이스마다 0<=middle<=test_case 까지 반복문을 돌아 줍니다.

여기서 middle은 위의 a+b+a에서 b와 같이 중앙에 오는 숫자입니다.

양 옆은 (test_case - middle)//2가 됩니다.( (test_case - middle)%2==0일 경우만 )

 

그렇다면 middle이 i일 경우 재귀적인 팰린드룸의 개수는 dp[(test_case - i)//2]가 될 것입니다.

(양 옆이 (test_case - middle)//2 이고, 위의 아이디어에서 (test_case - middle)//2를 재귀적인 팰린드룸으로 또 나타낸다면 이것은 test_case에 대한 재귀적인 팰린드룸이 되는 것이기 때문입니다.)

 

반복문을 돌면서 이전에 계산한 dp 값을 사용한다면, dp[test_case]가 답이 됩니다.

 

 

 

해결

dp를 이용한 풀이를 또 연습해볼 수 있어 좋았습니다!

 

문제 링크 : https://www.acmicpc.net/problem/2705

2705번: 팰린드롬 파티션

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/2705.py