코딩 연습

프로젝트 오일러 145번 본문

project euler with python

프로젝트 오일러 145번

코딩아저씨 2016. 3. 15. 16:10
반응형

Some positive integers \(n\) have the property that the sum \([n+{\rm reverse}(n)]\) consists entirely of odd (decimal) digits. For instance, \(36+63=99\) and \(409+904=1313\). We will call such numbers reversible; so \(36, \; 63, \; 409\), and \(904\) are reversible. Leading zeroes are not allowed in either \(n\) or \({\rm reverse}(n)\).

There are \(120\) reversible numbers below on-thousand.

How many reversible numbers are there below on-billion \(\left ( 10^9 \right )\)?




자연수 \(n=123\) 에 대해서 자연수 \(n\) 을 역순으로 만든 수 \(321\)을 \({\rm reverse}(n)\) 이라고 하자. 어떤 자연수는 \(n + {\rm reverse}(n)\) 의 모든 자리수가 홀수가 되는 특징을 갖는다. 예를 들어, \(36+63=99\) 이고 \(409+904=1313\) 으로 이런 특징을 갖는 자연수이다. 이런 특징을 갖는 자연수를 reversible 하다고 할 때, 위의 예에서 봤던 네 수 \(36, \;63, \;409, \;904\) 는 모두 reversible 한 수들이다. 물론 맨 앞자리가 \(0\) 이 되는 경우는 생각하지 않는다.

\(1000\) 미만의 자연수 중 reversible 한 자연수는 모두 \(120\) 가지가 있다.

\(10^9\) 미만의 자연수 중 reversible 한 자연수는 모두 몇 개인가? 


처음에 이 문제는 모든 자연수를 하나하나 reversible 인지 확인하면서 풀게 되는 것이 정상(?)적인 인간의 풀이법이다. 그렇지만 그 방법은 인간의 인내심이라는 변수를 고려하지 않은 방법이기 때문에 일명 암 걸리게 하는 풀이법이 된다. 따라서 다음과 같은 방법으로 접근해야만 건강한 삶을 계속적으로 유지할 수 있다.


이 문제에서는 최대 9자리 자연수까지만 고려하면 된다. 또한 \(n\) 자리의 자연수를 \(a_1 a_2 a_3 \cdots a_n\) 이라고 표현하기로 한다면, \(a_1 + a_n\) 은 일의 자리수를 결정하게 되므로 무조건 홀수가 되어야 한다. 그리고 \(a_2 + a_{n-1}\) 은 절대로 \(10\) 이상의 수가 되어서는 안된다. 그렇게 되면 \(10^{n-1}\) 자리가 짝수가 되기 때문이다.  


1) 자릿수가 \(4k+1\;\;(k=0, \;1, \;2)\) 자리인 경우 - reviersible 은 없다.


① 자릿수가 한 자리인 경우

똑같은 수가 더해지므로 무조건 짝수가 되어 reversible 할 수가 없다.


② 자릿수가 다섯 자리인 경우


중간에 \(a_3\) 가 두 번 더해지므로 짝수가 된다. 따라서 반드시 \(a_2 + a_4\) 는 \(10\) 이상의 홀수가 되어야 한다. 그런데 이렇게 되면 만의 자리수가 짝수가 되어 안된다. 따라서 이 경우에도 reversible 한 수는 찾을 수 없다.


③ 자릿수가 아홉 자리인 경우

중간에 \(a_5\) 가 두 번 더해지므로 짝수가 된다. 따라서 \(a_4 + a_6\) 는 \(10\) 이상의 수가 되어야 한다. 따라서 \(a_3+a_7\) 은 짝수가 되어야 하고, \(10\) 의 자리를 만드는 \(a_2 + a_8\) 이 \(10\) 이상이 되어야만 한다. 그런데 위에서 살펴 봤듯이 \(a_2 + a_8\) 은 \(10^7\) 자리수를 만드는데, 여기서 \(10\) 이상의 수가 나오게 되면 \(10^8\) 자리가 짝수가 되기 때문에 안된다. 결국 여기서도 reversible 은 찾을 수 없다.


2) 자릿수가 \(2k\)  (\(k=1,\; 2, \; 3, \; 4\)) 자리인 경우 - \(20 \times 30 ^{k-1}\) 

이 경우는 모든 자리의 합이 \(10\) 을 넘지 않는 홀수여야 한다.


① 자릿수가 두 자리인 경우


\(a_1 + a_2\) 가 \(10\) 이상의 홀수가 되면 \(10\) 의 자리 수가 짝수가 되어 안된다. 따라서 \(a_1+a_2\) 는 \(10\) 미만의 홀수가 되어야 한다. 단 \(a_1\) 이나 \(a_2\) 가 \(0\) 이 되면 안된다. 따라서 가능한 수는 \(20\) 가지가 된다. (12, 14, 16, 18, 32, 34, 36, 52, 54, 72 과 그 reverse 들까지 총 20개)


② 자릿수가 네 자리인 경우

\(a_1+a_4\) 가  \(10\) 이상의 홀수가 되면 \(a_2 + a_3\)가 짝수가 되어야 하는데, \(10\) 미만의 짝수면 \(100\)의 자리가 짝수가 되어서 안되고, \(10\) 이상의 짝수면 천의 자리가 짝수가 되어 안된다. 따라서 \(a_1+a_4\)와 \(a_2+a_3\) 는 모두 \(10\) 미만의 홀수가 되어야 한다. 이때, \(a_1\) 과 \(a_4\) 는 \(0\) 이면 안되지만 \(a_2\) 나 \(a_3\) 는 \(0\) 이어도 관계없다. \((a_1, \; a_4)\) 의 순서쌍은 \(20\)개, \((a_2, \;a_3)\) 순서쌍은 \(30\) 개가 되어 총 \(20 \times 30\) 개의 reversible 이 존재한다.


③ 자릿수가 여섯 자리인 경우

\((a_1, \;a_6)\), \((a_2, \; a_5)\), \((a_3, \; a_4)\) 세 개의 순서쌍을 고려하면 된다. 이 세 개의 순서쌍 중 어떤 것이라도 그 합이 \(10\) 이상이 조건에 맞지 않는 것을 알 수 있다. (이 부분은 각자 해 보는 것이 좋겠다. 절대로 귀찮아서 이러는거다.) 따라서 세 개의 순서쌍 모두 그 합이 \(10\) 미만의 홀수가 되어야 하므로 \((a_1, \; a_6)\) 순서쌍은 \(20\) 개, 나머지는 \(30\) 개 하여 총 \(20 \times 30 ^2\) 개의 reversible이 존재한다.


④ 자릿수가 여덟 자리인 경우

마찬가지로 어떤 순서쌍도 \(10\) 이상이 되어서는 안된다. 이것도 각자 해 보는 것이 좋겠다. 따라서 \(20 \times 30^3\) 개의 reversible 이 존재하는 것을 알 수 있다.


결국 \(n\) 이 짝수일 때, \(n\) 자리 자연수 중 reversible한 수의 개수는 \(20 \times 30 ^ {\frac{n}{2}-1}\) 개가 된다. 


3) 자릿수가 \(4k+3\;\; (k=0, \; 1)\) 인 경우 - \(100 \times 500^k\)


① 자릿수가 세 자리인 경우

가운데 \(a_2\) 가 두 번 더해지므로 짝수가 된다. 따라서 \(a_1 + a_3\) 는 \(10\) 이상의 홀수가 되어야 한다. \(a_2+a_2\) 가 \(10\) 이상이 되어서는 안되므로 \(10\) 미만의 짝수가 되어야 한다. 따라서 \(a_2\) 가 가질 수 있는 값은 0, 2, 4, 6, 8 의 다섯 가지이다. 결국 \(20 \times 5\) 개의 reversible 이 존재한다.


② 자릿수가 일곱 자리인 경우

세 자리인 경우와 마찬가지로 \(a_4 + a_4\) 가 짝수이므로 \(a_5+a_3\) 가 \(10\) 이상의 수가 되어야 하고, 이 경우 \(a_2 + a_6\) 는 \(10\) 미만의 짝수가 되어야 한다. 이때, \(a_1 + a_7\) 이 \(10\) 이상의 홀수가 되면 가능하다. 따라서 \(5 \times 20 \times 20 \times 25\) 개의 reversible 이 가능하다. 


def nofreversible(n):
    if n % 4 == 1:
        return 0
    if n % 4 == 3:
        return 100 * 500 ** (n // 4)
    if n % 2 == 0:
        return 20 * 30 ** (n // 2 - 1)

sum = 0
for i in range(1, 10):
    sum += nofreversible(i)

print(sum)


반응형

'project euler with python' 카테고리의 다른 글

프로젝트 오일러 147번  (0) 2016.03.15
프로젝트 오일러 146번  (0) 2016.03.15
프로젝트 오일러 144번  (0) 2016.03.15
프로젝트 오일러 143번  (0) 2016.03.15
프로젝트 오일러 142번  (0) 2016.03.15


Comments