5월21일 #Palindrome DP

1. Palindrome DP

팰린드롬https://www.acmicpc.net/problem/1243

팰린드롬의 개수https://www.acmicpc.net/problem/1204

팰린드롬 문장https://www.acmicpc.net/problem/1054

N개의 문자열을 붙여 만들 수 있는 팰린드롬의 개수를 구하는 유형.
1054는 단어를 1번씩만 사용 가능한 것이 차이점이다.

dp 상태를 정하기에 앞서 관찰을 해보면
항상 dp는 한 단어를 정하고 이를 사용하는데서 시작한다.
단어를 앞/뒤에 번갈아 붙이게 된다.

첫 단어 이후부터는 조건이 생긴다.
가령 abcd라는 단어를 골라서 앞쪽에 붙였다고 하면
뒤쪽에 dcba를 접미사로 가지는 문자열이나 dcba의 접미사인 문자열만 뒷쪽에 붙일 수 있다.
이런 식으로 계속 붙여 나가다 보면 붙일 문자열의 접미사 / 접두사 조건이 생기는 것을 알 수 있다.

팰린드롬 문제를 예시로 들면 길이, 남은 문자열, 접두사/접미사 여부 3가지 요소를 상태로 정의하는 dp 점화식을 세울 수 있다.

자세한 풀이는 ruz님의 블로그를 보고 많이 배웠다. 이곳을 참고하기 바란다.
https://aruz.tistory.com/26

2. Dendroctonus

https://www.acmicpc.net/problem/15170

15170번: Dendroctonus

예전에 최소 외접원 알고리즘을 공부할 때 한창 꿀빠려다가 실패한 문제다.
많은 이들이 나와 같은 루트를 탔을 거다. 15%라는 굉장히 낮은 정답률을 자랑한다.
결론적으로, 이 문제는 최소 외접원을 구하는 알고리즘 자체를 사용하는 문제가 아니다.

'I' 점들의 최소 외접원을 구해서 'N' 점들이 포함되는지 체크만 하면 된다고 착각하기 쉬운데,
꼭 최소 외접원보다 큰 원만이 답이 되는  케이스가 존재하기 때문에 틀리다.
 ex) (0,0) (0,4) 가 'I'  (2,1)이 'N'이면 최소외접원은 정답의 원이 될 수 없다. (2,1)을 포함하지 않는, 아래로 큰 원을 고르면 된다.

그런데 그런 원들 중에서도 최소 크기의 원이 존재할 것이다. 이때 그 원은 I' 색의 점들뿐만 아니라 'N' 색의 점도 지날 것을 분석할 수 있다. 최소 외접원은 주어진 점집합 중 최소 2개의 점을 포함한다는 사실을 이용하자.
일반적인 N^4 최소 외접원 알고리즘처럼 Brute-Force로 2개씩 골라 원 만들기, 3개씩 골라 원 만들기를 시행하면서 조건을 만족하는 원( 'I'는 모두 안에, 'N'은 모두 밖에 ('I', 'N' 모두 경계선에 걸쳐도 된다))이 있는지 조사하면 된다.

N <= 100이지만 NC3 ~ N^3 / 6 + 조건 미충족 점이 있을 시 바로 for문 break되는 특성 때문에 빠른 시간 안에 알고리즘이 수행된다.