1️⃣서론
백준 문제 1629번 곱셈 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣문제 설명
자연수 A를 B번 곱한 수를 C로 나눴을 때의 나머지를 구하는 방법입니다.
3️⃣풀이
이 문제는 그냥 단순하게 A를 B번 곱하면 수가 매우 커지게 되므로 단순하게 곱해서는 안됩니다.
A를 B번 곱했다고 하면 경우의수로 B가 짝수일 때와 홀수일 때로 나눌 수 있습니다.
- 만약 B가 짝수이면
A ** B = A ** B // 2 ** 2입니다. - 만약 B가 홀수이면
A ** B = A ** B * A입니다.
이를 활용해 B를 줄여 나가면서 우리는 나머지를 구할 수 있습니다.
이렇게 계속 B를 줄여나가다가 B가 0이나 1이 될때까지 분할정복을 수행하면 답을 찾을 수 있습니다.
그럼 소스코드를 살펴보겠습니다.
4️⃣ 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def mul(a, b):
if b == 0:
return 1
elif b == 1:
return a
elif b % 2 > 0:
return mul(a, b - 1) * a
else:
d = mul(a, b // 2)
d %= c
return d ** 2 % c
a, b, c = map(int, input().split())
print(mul(a, b) % c)
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
