BOJ 3719 팰린드롬 날짜

먼저, 윤년을 고려하여 연, 월, 일이 주어졌을 때 올바른 날짜인지를 판별하는 함수 is_valid_date를 작성합니다.

이제 다음과 같이 경우를 나눌 수 있습니다.

• 연도가 5자리 이하인 경우: 전체가 9자리 이하이고, 그 중에서 팰린드롬은 최대 10만 개 정도가 있으므로, 모든 팰린드롬을 검사하여 올바른 날짜들을 사전순으로 모두 모아놓을 수 있습니다.
• 연도가 6자리 이상인 경우: 연도의 앞 4자리는 뒤집었을 때 MMDD와 같아야 하고, 나머지 자리는 그 자체로 팰린드롬이어야 합니다.

(사실 4자리를 기준으로 나눠도 되는 것으로 보이지만, 실제 구현을 기준으로 설명합니다.)

입력의 연도가 5자리 이하라면, 첫 번째 경우에서 모아놓은 모든 날짜 중에서 입력의 바로 다음에 있는 것을 이분 탐색으로 구합니다. 그러한 날짜가 없다면, 답은 100100년 10월 01일입니다. 1월 1일에 해당하는 연도가 정답이 아님에 유의합니다.

그 외의 경우, 먼저 연도를 첫 4자리와 나머지로 나눕니다. 그렇게 나누었을 때 앞 4자리의 값을 $Y_1$, 나머지 부분의 값을 $Y_2$, 나머지 부분의 길이를 $\ell$이라고 합시다. 그리고 어떤 4자리 값 $x$를 뒤집었을 때 앞 2자리를 $M(x)$, 뒤 2자리를 $D(x)$라고 합시다.

각 연도에 대해 가능한 팰린드롬 날짜는 최대 1개임($Y_1$을 뒤집어서 날짜로 두었을 때 올바른 날짜이면 1개, 아니면 0개)을 이용하여, 입력과 가장 가까운 팰린드롬 날짜는 다음의 순서로 고려할 수 있습니다. 여기서 “올바른 날짜"는 2월 29일을 포함합니다.

• 먼저, 연도를 그대로 둘 수 있는지 확인합니다. $(10^\ell Y_1 + Y_2, M(Y_1), D(Y_1))$이 올바른 날짜이면서 입력보다 크면, 이것이 답입니다.
• 그 다음으로, $Y_1$을 그대로 둘 수 있는지 확인합니다. 길이 $\ell$의 팰린드롬 중 $Y_2$를 초과하는 최소의 팰린드롬을 $Y_2'$라고 할 때, $(10^\ell Y_1 + Y_2', M(Y_1), D(Y_1))$이 올바른 날짜이면 이것이 답입니다.
• 그 다음에는 $Y_1$을 옮겨 봅니다. $Y_1$보다 큰 연도 중에서 $(M(Y_1'), D(Y_1'))$이 올바른 날짜(2월 29일 포함)인 것을 찾아서, $(10^\ell Y_1', M(Y_1'), D(Y_1'))$이 올바른 날짜이면 이것이 답입니다.
• 이것도 안 되면 연도의 자리수가 같은 범위 내에는 답이 없다는 뜻이므로, $(1001 \times 10^{\ell + 1}, 10, 01)$이 답이 됩니다.

각각의 경우에서, 윤년이 아닌데 2월 29일을 선택했을 가능성이 있습니다. 이때는 이 전체 과정의 맨 처음으로 돌아가서 다음 올바른 날짜를 찾기를 반복해야 합니다.

가장 가까운 연도, 가장 가까운 날짜 등은 맨 처음에 가능한 올바른 값들을 모두 배열에 모아 놓은 뒤에 이분 탐색을 하는 것으로 해결할 수 있습니다.