백준 소수인팰린드롬 : 팰린드롬인지 먼저 검사한다.

 안녕하세요. 조경완입니다. 백준에서 문제들을 풀다 보면, 소수인팰린드롬 문제도 보셨으리라 생각합니다. 어렵지 않은 문제이지만, Loop를 칠 때, 어떻게 치면 좋은지 생각해 볼 수 있는 문제인 듯 싶어서 가지고 오게 되었습니다.

 

---

 문제는 아래와 같습니다.

 

 최악의 경우에는 a가 5, b가 1억이니 만만치 않은 문제인 듯 싶습니다. 그런데, 314명이 풀어냈습니다. 1억까지를 에라스토스테네스의 체로 거른다고 해도 힘들고, 그렇다고 팰린드롬을 로그 복잡도로 판별하고 루트 복잡도로 소수임을 판별하자니. 그것도 힘듭니다. 어떻게 하면 좋을까요?

 

 아이디어는 의외로 단순합니다.

 

 일례로 99823419가 소수인지 판단하는 것은 쉽지 않습니다. 그런데, 팰린드롬인지는 어떻게 판정하면 되나요?

 

 

 그냥 뒤에서 부터 본 문자랑 앞에서 본 문자가 같은지만 체크해 주면 됩니다. O(자릿수)만큼 걸리니 로그 복잡도를 가집니다. sqrt와 로그 복잡도. 그냥 팰린드롬인지 먼저 거르는 게 나을 듯 싶습니다. 그런데, 1억개의 수 중에서, 팰린드롬인 것이 9999만 9999개였다면, 거르는 의미가 사실 없습니다.

 

 

 예를 들어서, 팰린드롬이 아니라는 조건을 먼저 검사했다고 해 보겠습니다. 이 조건을 검사하는데 p만큼의 비용이 듭니다. 그런데, 팰린드롬인 것이 9999만 9999개가 있었다면, 9999만 9999개에 대해서 5번째 줄인, is_sosu 메서드를 또 호출하게 됩니다. 즉, 1억개의 수가 있었을 때, 100,000,000p + 99,999,999s 만큼의 비용이 듭니다.

 

 그런데 반대로 이렇게 되면 어떻게 될까요?

 

 

 그러면, 1억개 중 1천만개에 대해서만 palindrom 함수를 추가로 호출하게 되므로, 100,000,000s + 10,000,000p만큼 들게 됩니다. s의 비용이 1만, p의 비용이 10이라고 칩시다. 그러면 전자인 경우, 10억 + 9999억이 들 겁니다. 후자라면 9999억 + 1억만큼 들 겁니다. 즉, 팰린드롬이 아닌 것이 거의 없다면, 팰린드롬이 아니면 빠져 나오는 로직을 먼저 넣었다고 크게 개선되지는 않습니다.

 

 하지만, 생각보다 팰린드롬 가짓수는 많이 적음을 간파하실 수 있습니다. 왜냐하면 어짜피 조건을 만족하는 수는 커봤자 8자리 수입니다. 그러면, 수는 아래와 같은 형태 중 하나일 겁니다.

 

 i + rev_i이거나

 

 아니면 i + c + rev_i이거나. 여기서 c는 숫자입니다. 홀수 자리인 경우에는, 예를 들어 9993999일 때에는 [9993]999. 즉 9993으로 보고, 짝수 자리일 경우에는 [339]933. 이렇게 반으로 쪼개서 보겠습니다. 홀짝, 홀짝, 홀짝, 홀짝이 번갈아 나타나고, 규칙을 잘 찾아보면, 홀짝 한 사이클이 돌 때 마다 [(i+1)/2]자리인 자연수가 2번 나옵니다.

 

 1부터 9999까지의 자연수의 갯수에 2를 곱하면 19998개이므로, 19998개에 대해서만 보면 됨을 알 수 있습니다. 1억 vs 19998. 팰린드롬이 1억개 중에 2만개 정도밖에 없습니다. 9998만개에 대해서는 걸러버릴 수 있다는 소리입니다. 9998만개에 대해서 순회하는 것 조차 낭비이므로, 조건을 만족하는 팰린드롬 수 2만개만 가지고 소수인지 보면 됩니다. 이를 코드로 대강 짜보면 아래와 같습니다.

 

 

 중간 위치의 자릿수가 mid의 역할을 합니다. 그리고 zari는 자릿수를 의미합니다. 홀수 자릿수인 경우, 중간에 0, 1, 2, 3, 4, 5, 6, 7, 8, 9가 들어갈 수 있으므로, 이에 대한 처리를 해 주어야 합니다. i값은 t가 339933일 때, 339이고, t가 3395933일 때 339입니다. 절반을 기준으로 앞에 부분을 취한다는 것을 알 수 있습니다.

 

 

 그러면 main 함수에서는 자리가 짝수일 때에만 자릿수를 올려주면 될 겁니다. mid값이라고 봐도 무난하겠군요. 그리고 from과 to도 짝수 자리일 때만 10을 곱한다는 것을 주목하시면 됩니다. 팰린드롬 수를 채우는 부분은 3년 전에 짜서 지저분 하네요. 이 부분은 자릿수별로 dfs를 돌릴 때 양 끝부터 채워나가는 식으로 코드를 리팩토링 할 수 있습니다.

 

 

---

 이제, 2만개의 후보해에 대해서 소수인지 검사를 하면 됩니다.

 

 

 이에 대한 소스는 위와 같습니다. 그런데, 여기서 하나 더 생각해 볼 만한 것은 최악의 경우에 1만개의 수에 대해서 나누어 떨어지는지 검사할 것인데. 그럴 필요가 전혀 없다는 것입니다. n이 소수 a로 나누어 떨어지지 않는다면, 소수 a에 어떠한 자연수 q를 곱한 aq로도 나누어 떨어지지 않습니다.

 

 이는, n이 aq로 떨어지면, n = aqQ = a(qQ)이므로 a로 떨어진다는 대우 명제를 이용하면 쉽게 증명하실 수 있습니다. 1만까지 수 중에서 소수인 것의 갯수는 몇 개일까요?

 

 

 1229개입니다. 1만개에 비하면 꽤 작은 수입니다. 2만개에 대해서 1229번 loop를 다 돈다고 해도 2500만 단위 연산밖에 하지 않습니다. 시간 내에 넉넉하게 들어옵니다.