홀수 위치 자리수들과 짝수 위치 자리수들의 곱이 서로 같은 n자리 자연수 찾는 마법같은 방법(중간에서 만나기)

14108번: Umnozak (acmicpc.net)

 

n자리 자연수중에서 짝수 위치의 자리수들의 곱과 홀수 위치의 자리수들의 곱이 서로 같게되는 그러한 자연수들의 개수를 구하는 문제

 

첫번째 자리는 홀수 위치라고 가정

 

1자리 자연수는 홀수 위치밖에 없으니 0개

 

2자리 자연수는?

 

11,22,33,44,55,66,77,88,99로 9개

 

3자리 자연수는?

 

100부터 999까지 전수조사해보는게 나을 것 같다

 

count = 0

for i in range(100,1000):
    
    s = str(i)
    
    a = 1
    b = 1
    
    for j in range(len(s)):
        
        if j % 2 == 0:
            
            a *= int(s[j])
        
        else:
            
            b *= int(s[j])
    
    if a == b:
        
        count += 1

print(count)

 

 

이러면 32개가 나옴

 

이렇게 전수조사하면 4자리는 380개, 5자리는 4097개, 6자리는 54054개, 7자리는 700099개,....

 

7자리부터는 시간이 좀 걸리더라 30초 넘게 걸렸고

 

8자리는 6분...

 

9자리는 2시간...

 

10자리는 12시간...

 

n = 14까지 찾아야하는데 이렇게는 못찾지

 

하지만 짝수 위치의 자리수 곱들과 홀수 위치의 자리수 곱들이 서로 같은 경우를 찾으면 되니까

 

각 위치에 들어갈 수 있는 수는? 0~9로 10가지

 

물론 첫번째 자리는 0이 들어갈 수 없어서 1~9 9가지

 

다음과 같이 접근하면 어떨까?

 

8자리의 경우 x1x2x3x4x5x6x7x8에서 x1,x2,x3,x4,x5,x6,x7,x8 8자리 각각에 0~9를 하나 넣으면 결정할 수 있다

 

여기서 짝수 위치의 자리는 x2,x4,x6,x8

 

홀수 위치의 자리는 x1,x3,x5,x7

 

따라서 짝수 위치의 자리 (x2,x4,x6,x8)를 만들면 $10^{4}$가지를 만들 수 있고

 

홀수 위치의 자리 (x1,x3,x5,x7)를 만들면 $10^{4}$가지를 만들 수 있다

 

이렇게 만든 $10^{4}$가지 각각에서 곱이 서로 같은 경우의 가지수를 서로 곱하면 충분하다

 

이렇게 하면 $O(10^{9})$ 걸리던 것을 $O(10^{4})$만에 해결할 수 있다

 

예를 들어 서로 곱해서 6을 만드는 방법이

 

(1,1,2,3), (1,2,3,1), (6,0,1,1), (6,1,1,1),....로 16가지 있는데

 

짝수 위치에서 (1,1,2,3)에 대하여 홀수 위치 (1,1,2,3), (1,2,3,1), (6,0,1,1), (6,1,1,1),.... 16가지 가능하고

 

짝수 위치에서 (1,2,3,1)에 대하여 홀수 위치 (1,1,2,3), (1,2,3,1), (6,0,1,1), (6,1,1,1),.... 16가지 가능하고

 

....

 

짝수 위치 A에 대하여 홀수 위치 A1,A2,A3,...,A16 16가지 가능하므로

 

총 16*16가지 곱사건이라는 말

 

odd = {}

for x1 in range(1,10):
    
    for x3 in range(10):
        
        for x5 in range(10):
            
            for x7 in range(10):
                
                v = x1*x3*x5*x7
                odd[v] = odd.get(v,0) + 1

even = {}

for x2 in range(10):
    
    for x4 in range(10):
        
        for x6 in range(10):
            
            for x8 in range(10):
                
                v = x2*x4*x6*x8
                even[v] = even.get(v,0) + 1


count = 0

for a in odd:
    
    for b in even:
        
        if a == b:
            
            count += (odd[a]*even[b])

print(count)

 

 

이렇게 하면 8자리를 찾는데 $O(10^{4})$정도에 가능하고 8742818가지 나온다는 것을 알 수 있다

 

6분 걸리던 것을 1초도 안걸리고 계산하는 마법같은 일이 일어난다

 

이런 식으로 N이 14개밖에 없으므로 N = 1,2,3,4,..,14까지 모두 미리 계산해두고 제출하면 된다