이 문제의 의도는 쉬워보이는 척 (실제로도 쉽지만) 하면서 마음이 급한 참가자들을 낚기위함 이었습니다.
-_-; 스코어 보드를 보니 제 목표는 달성한 듯 합니다. (D를 빨리 풀어줘서 더 많은 참가자들이 떡밥을 물게 해준 2등팀에게 감사드립니다)
이 문제의 풀이는 의외로 간단합니다. 우선 몇 가지 observation이 필요합니다.
주어진 n과 k, 그리고 정답 m을 생각해 봅시다. (m은 anagram of n)
m의 가장 큰 자리 부터 k와 비교를 할 때 3가지 경우가 가능합니다
1) k보다 작다
2) k와 같다
3) k보다 크다
3)의 경우, m의 나머지 숫자들 (즉 현재 자리수보다 작은 자리에 있는 숫자들)은 비내림차순 정렬이 되어있어야 합니다. 아니라면, 정렬 안된 숫자들을 정렬해서 m보다 더 작은 m'을 만들 수 있고, m' 이 m보다 lucky lucky number에 가깝습니다.
비슷하게 1)의 경우, 현재 자리수보다 작은 자리에 있는 숫자들은 비오름차순 정렬이 되어야 합니다. 아니라면 그 수들을 정렬해서 m보다 더 큰 m'을 만들 수 있고 m'이 m보다 lucky lucky number에 가깝습니다.
2)의 경우, tie-break가 일어나는 (1이나 3의 경우에 해당하는) 자리수 까지 가는 경우가 있고 혹은 정답 m (그리고 n)이 아예 lucky lucky number인 경우가 있습니다.
어쨌거나 정답에 대한 observation이 힌트를 줍니다 (backtracking):
첫 자리 수로 어떤 수 x를 시도했을 때:
1) x 2) x=k, then 다음 자리 수 try
3) x>k, then sort the rest (정순)
이 backtracking이 찾아내는 모든 답을 lucky lucky number랑 비교하면서 가장 근접한 (그 중에 가장 큰) 수를 찾으면 답이 됩니다.
그런데 잠깐, 만약 주어진 수 n이 몇 개의 k를 포함했을 경우, 그 'k'들은 정답에서 어디에 위치할까요? 가장 큰 자리수들에 자리합니다. 간단하게 증명할 수 있습니다. 첫 자리수가 k로 시작하는 anagram C, 첫 자리수가 k보다 큰 a로 시작하는 anagram A, k보다 작은 b로 시작하는 anagram B 세 가지를 생각해 봅시다.