[python/파이썬] 백준 1225 이상한 곱셈

[문제 출처]

https://www.acmicpc.net/problem/1225

1225번: 이상한 곱셈

 

[문제 풀이]

두 개의 수가 주어졌을 때, 각 자리별로 곱해서 합을 구하는 문제이다.

예를 들어 12x45 라면

일반적으로는 10x4 + 10x5 + 2x4 + 2x5로 계산하지만 

이 문제에서는 1x4 + 1x5 + 2x4 + 2x5 로 계산한 결과를 출력해야 한다.

 

🧠소스 코드1 - 시간 초과

> 단순하게 문자열로 두 입력을 받아서 이중 for문으로 계산해 보았으나 역시나 시간 초과가 발생했다.

#1225

a, b = input().split()

result = 0
for i in a:
  for j in b:
    result += (int(i)*int(j))

print(result)

 

🧠소스 코드2 - 맞았습니다!!

> 시간을 줄이기 위해서 두 수 중에 한 수의 각 자릿수의 합을 구해서 다른 수랑 곱하는 방법으로 바꿔보았다.

1x2 + 1x3 은 1x(2+3) 와 동일하기에 한 수의 자릿수들의 합을 구해 다른 수의 각 자릿수와 곱하도록 하였다.

 

예를 들어 

121 x 34 라면

1×3 + 1×4 + 2×3 + 2×4 + 1×3 + 1×4 = 28과 같이 답을 구해야 한다.

이 식을 다르게 쓰면 

1x(3+4) + 2x(3+4) + 1x(3+4) = 28 이 된다.

(3+4)는 반복되므로 미리 계산하여 사용하여 시간을 단축하였다.

 

위의 식은 (1+2+3)x(3+4)로도 바꿔 쓸 수 있으며, 이 식을 이용하면 아래의 코드에 있는 while문 코드를 2번 사용해서도 풀 수 있다.

그러나 메모리가 줄어든다거나 시간이 줄진 않는다.(시간은 조금 더 소요됨)

# 1225
 
a, b = input().split()
 
b = int(b)
sum_b = 0
while b>0:
  sum_b += (b%10)
  b //= 10

result = 0
for i in a:
  result += (int(i)*sum_b)

print(result)