BOJ 2705, 팰린드롬 파티션
ProblemSolving ·이 문제는 DP문제 입니다.
풀이
처음에는 재귀로 완전탐색할까 생각했었습니다. 하지만 시간초과가 날 것 같아 어떻게 해야하지 고민을 하던중 친구가 식만 세우면 된다라는 말을 해주어서 DP를 생각해서 문제를 해결하였습니다.
식을 어떻게 세웠냐!
팰린드롬 가운데 오는 숫자가 있고 그 값을 제외한 합의 나누기 2 만큼의 팰린드롬이 양쪽에 있을 겁니다.
이런 규칙을 생각해보았을때 (n의 팰린드롬이 가능한 경우의 수가 dp[n]입니다.)
dp[15]라면 dp[1]+dp[7] + dp[3]+dp[6] + dp[5]+dp[5] + dp[7]+dp[1] 이 답이 겠죠?
(양쪽의 팰린드롬은 똑같이 생겼기때문에 한번만 더해줍니다.)
여기서 주의할 점이 2가지가 있습니다.
-
양쪽에 팰린드롬이 만들어져야하므로 i-j는 짝수여야한다!
-
자기 자신은 식에 포함되지 않았으므로(식에 2를 나누는 연산이 있기때문에 자기자신은 들어갈 수 없다.) 초기값을 1로 설정해준다!
#include<stdio.h> int t, n, dp[1001]; int main() { for (int i = 1; i <= 1000; i++) dp[i] = 1; for (int i = 2; i <= 1000; i++) for (int j = 0; j <= i; j++) if ((i - j) % 2 == 0) dp[i] += dp[(i - j) / 2]; scanf("%d", &t); while (t--) { scanf("%d", &n); printf("%d\n", dp[n]); } return 0; }