[ICPC 본선 대비 뇌셋] Day 10

백준 16326번 Numbers www.acmicpc.net/problem/16326

16326번: Numbers

마찬가지로 NEERC set을 돌다가 만난 문제인데, 코딩은 좀 복잡할 것 같아 풀이만 남긴다. 레프 화이팅><

$N = x + y$에서 x, y가 각각 팰린드롬일 때 가능한 (x,y) 순서쌍의 개수를 구하는 문제이다.

문제를 보면 자릿수를 따라가면서 dp를 돌면 되나? 라는 생각을 하지만 어림도 없다. 간단한 관찰로부터 결과를 얻어내자.

[정의 1] 반쪽수열: 팰린드롬 수열의 오른쪽 절반을 반쪽수열이라고 정의하자.

[시도 1] N보다 작은 팰린드롬의 개수는 $\sqrt(N)$개정도 되기 때문에, x를 고정시키고 N-x가 팰린드롬인지 확인한다.

시간복잡도는 $10^9$정도이고, 당연히 똑떨이다.

따라서 다음 시도는 DP를 이용하여 경우의 수를 줄이는 방법을 생각할 수 있다.

[시도 2] 시도 1과 같이 먼저 둘 중 하나의 크기가 $10^{12}$보다 작다면, x를 $10^6$번 노가다를 뛰어서(나타낼 수 있는 범위는 $10^{12}$정도이다.) 가능한 팰린드롬 쌍을 전부 구한다. 두 팰린드롬의 크기가 전부 $10^{12}$보다 크다면, x(>y)의 반쪽수열의 6자리 suffix로 가능한 가짓수는 $10^6$이다. 한편 x의 반쪽 수열의 크기도 $10^6$보다 큼이 보장되므로, y의 6자리 suffix도 그와 같다.

N에서 팰린드롬 수열 x(>1e6)의 일부와 y(>1e6)의 일부를 뺀 결과는 위 검은색 블록과 같아야한다.

 

따라서 x와 y의 suffix가 고정되었으므로, x와 y를 뺐을 때 위의 그림에서 작은 검은색 상자(빨강 부분을 제외한 자리에서 1칸 왼쪽으로 넓어진 범위이다.)만 남아있어야 한다. 이것이 가능한 y의 왼쪽 블럭의 위치는 두 개 이하로 결정된다.

이제 남은 일은 빨강과 파랑의 나머지 부분을 채워주는 일이다. 각각 $10^6$보다 작으므로, 고려해줘야하는 총 가짓수는 $($10^3$)^2$가지 정도이다. 이를 미리 dp table로 채워넣어주면 끝.

따라서 O($N^{1/3}$)에 가능하다.