포함배제의 원리1 dp with 포함배제 원리 포함배제 원리를 이용하는 dp문제 2개를 풀어보자. 1. BOJ 14517 https://www.acmicpc.net/problem/14517 14517번: 팰린드롬 개수 구하기 (Large) 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다. 승수는 주 www.acmicpc.net [ 풀이 ] 문제를 잘 이해해야 한다. 부분수열이므로 연속된 팰린드롬일 필요가 없다. 맨처음과 끝에서 시작해서 좁혀가면서 갱신해주면 된다. dp[s][e]:=구간 [s,e]를 볼 때 팰린드롬의 총 개수라고 정의하면, 상태전이는 3가지가 있다. 1. s를 사.. 2022. 8. 1. 이전 1 다음