[Python] 백준 1225번(이상한 곱셈) 문제 풀이

 

 생각보다 많이 어려웠던 문제였다.

 

from itertools import product
a, b = input().split()
a, b = list(map(int, a)), list(map(int, b))
products = list(product(a, b))
for i in range(len(products)):
    products[i] = products[i][0] * products[i][1]
print(sum(products))

 

 일단 이렇게 한번 짜봤다. itertools의 product를 import하면 두 리스트에서 가능한 모든 조합을 반환해 주기에, 모든 조합을 구해서 곱한 뒤 그 합을 구했다. 결과는 메모리 초과. 이런. 9,999자리까지 입력이 가능한데 a와 b 둘 다 9,999자리로 오던가 한다면 당연히 메모리 초과가 뜰 수밖에 없을 것 같기는 하다.

 

a, b = input().split()
a, b = list(map(int, list(a))), list(map(int, list(b)))
s = 0
for i in a:
    for j in b:
        s += i*j
print(s)

 

 그래서 두번째 코드는 이렇게 짜봤다. 중첩 반복문을 이용하여 곱하고 더하고 한 것이다. 결과는 시간초과가 떴다. 이것도 생각해 보면 a와 b 둘 다 9,999자리가 오면 반복문을 99,980,001번을 돌려야 한다. 아무리 성능이 좋은 컴퓨터라도 이건 시간초과가 뜰 수밖에 없을 것 같다.

 

a, b = input().split()
a, b = list(map(int, list(a))), sum(list(map(int, list(b))))
s = 0
for i in a:
    s += i*b
print(s)

 

 그래서 이렇게 수학적으로 접근해봤다! 그냥 간단한 분배법칙을 쓰면 해결되는 문제였다. 이건 아무리 큰 수가 들어와도 최대 9999번밖에 반복을 안 하니 충분히 2초 안에 실행된다.

 

 어떤 원리를 사용한 것이냐 하면, 예를 들어, 세 자리 수 100a+10b+c와 두 자리 수 10d+e가 들어왔다고 해 보자. 그렇다면 문제에서 정의한 A*B를 하기 위해서는 ad+ae+bd+be+cd+ce를 해야 할 것이다. 여기까지 구현한 것이 아까 중첩 반복문을 사용한 코드였다. 그렇다면 이번에는 이걸 각각 a, b, c로 묶으면 a(d+e)+b(d+e)+c(d+e)만 해도 똑같은 값이 나오는 것을 알 수 있다...! 이러한 원리를 사용해서 문제를 풀었다.