백준 팰린드롬 진법 : 후보해는 생각보다 많이 적다.

오늘 풀어볼 문제는 백준 팰린드롬 진법이라는 문제입니다.

 

 난이도는 솔브드 기준으로 G3 ~ G1 정도 되는 문제입니다. x의 범위는 10^9입니다. 어떻게 풀어야 할까요?

 

---

 먼저, x가 적당히 작은 수일 때에는 굉장히 쉽습니다. 이 때 난이도는 S5에서 S4 정도 됩니다.

 

 

 그냥 2부터 n까지 z진법이 팰린드롬인지 검사하면 됩니다. zinbup 내부를 봅시다.

 

 

 yuki는 32개짜리 크기의 int형 배열입니다. zinbup 함수가 호출이 될 때 마다, 32개짜리 int형 배열을 초기화 시킵니다. 그리고 cur를 z로 나눠가면서 나머지 값만 계속 취합니다. 59 ~ 62번째 줄이 그러한 일을 수행합니다. p는 z진법으로 나타냈을 때 자릿수인데요. 팰린드롬이라면, 거꾸로 읽으나, 올바르게 읽으나 값이 같습니다. 적당히 실버5 ~ 실버4 정도 난이도를 줘도 될 듯 싶어요.

 

 그런데, 이것을 조금 더 최적화를 할 수 있는 방법이 있습니다. 10만을 500진법으로 표현하면 32자리까지 나올까요? 단 2자리만 나올 거에요. 따라서, 진법의 결과를 저장할 배열 yuki를 전역 배열로 선언을 해 놓습니다. x = 8, b = 2라고 해 봅시다.

 

 

 다음에, b = 3이라 해 봅시다. 8은 3진법으로 22입니다.

 

 

 그러면 p = 0으로 이동시키고 작업하면 됩니다. 이 때 복잡도는 어떻게 될까요?

 

 

 b진법이 x를 2자리로 표현할 때, b의 범위는 대충 x^1/2 ~ x입니다.

 

 

 b진법이 x를 3자리로 표현할 때, b의 범위는 어떻게 될까요? 대충 x^1/3 ~ x^1/2이라고 할 수 있어요.

 

 

 그러면, b진법이 x를 k자리로 표현할 때, b의 범위는 어떻게 될까요?

 

 

 b^(k-1) >= x일 때, x를 k자리로 표현할 수 있어요. 그런데, b^k <= x보다 작아야 하겠죠. 그러면 대략 b 값의 범위는 x^(1/k) ~ x^(1/(k-1))일 거 같네요. 봐야 하는 총 자릿수를 전개해 봅시다.

 

 이 때 초록색 부분은 무시할 수 있어요. 결국 x에 dominate 됩니다. 이는 그래프를 간단하게 그려봐도 알 수 있습니다.

 

 

 상수가 32에서, 감사하게도 2로 줄었어요. 따라서, x 값이 적당히 작다면 O(x)만에 풀 수 있습니다. 그런데, 제가 G3 ~ G1이라 한 것은 왜 그럴까요? x의 범위가 생각보다 꽤 큽니다. 그래서 단순히 naive하게 전수조사 하는 방법으로는 풀리지 않습니다.

 

 

---

 x가 10^9라면 어떻게 해야 할까요? 후보해를 어떻게 추려야 할까요? 잠깐 진법 시스템을 생각해 봅시다.

 

 

 b진법으로, x를 3자리로 표현할 수 있다면 어떤 관계식이 성립해야 할까요? b^2가 x보다 작거나 같아야 합니다. 그리고 어떻게 되어야 할까요? b^3이 x보다는 커야 합니다. 4자리로 표현할 수 있다면 어떻게 되어야 할까요?

 

 b^3 보다 x가 크거나 같아야 합니다. 또 b^4가 x보다는 커야 합니다. 그러면 x를 b진법으로 표현했을 때, 3자리 이상으로 표현되는 b의 갯수는 많아봤자 sqrt(x)개임을 알 수 있어요. 예를 들어 36을 3자리 이상으로 표현할 수 있는 진법은 2, 3, 4, 5, 6 이렇게 5개일 뿐입니다.

 

 

 z진법이 x를 2자리로 표현 가능한지 검사하는 함수는 is_two_zari입니다. 이제 이것을 가지고 x가 10^9일 때 어떤 진법으로 나타내야 팰린드롬이 되는지를 모두 구해 보겠습니다.

 

 

 먼저, n가 z진법으로 3자리 이상으로 표현할 수 있을 때에는 계속 22번째 줄에 걸리는 for loop를 돕니다. 최대 O(sqrt(n))번 돕니다. 다음에, n이 z진법으로 2자리로 표현될 때를 생각해 봅시다.

 

 

 그러면 대충 이런 상황입니다. Ab + A가 n과 같아야 합니다. A(b+1)이 n과 같아야 합니다. 이 때, A<b이고, b+1은 n의 약수여야 합니다. n의 약수를 구하기 위해서 우리는 sqrt(n)만에 구하는 알고리즘을 생각할 수 있습니다.

 

 

 저는 b를 Z로 두었습니다. 코드가 헷갈릴까봐. 하튼 이렇게 z를 구한 다음에, 자릿수에 들어가는 수 a가 진법을 나타내는 Z보다 작다면, z를 출력하면 됩니다.

 

 

 main 함수에서는 n의 범위에 따라서, 부르는 함수를 다르게 하면 됩니다.