[백준/Python]1629: 곱셈

문제

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

백준 단계별 풀이 - 분할 정복

---

풀이

자연수 A를 B번 곱한 값을 구하는 문제다. 단, 값이 매우 커질 수 있으므로 C로 나누어야 한다.

제한시간은 0.5초인데... 이걸 어떻게 분할하느냐?

 

만약 A, B가 2, 8로 주어졌다고 가정해보자.

8은 짝수이므로 단순히 반으로 쪼개주면 된다.

$ 2^8 $

$ = 2^4 * 2^4 $

$ = 2^2*2^2 * 2^2*2^2 $

가 될것이다.

 

홀수라면?

$ 2^5 $

$ = 2 * 2^4 $

$ = 2 * 2^2*2^2 $

가 되겠다.

 

즉, 짝수일땐 B//2를, 홀수일땐 A * B//2를 곱해주면 된다.

B가 0으로 주어질때 or B가 1일때 B//2는 자연수^0 = 1 이므로 1을 반환해주도록 한다.

# 메모리: 31120KB / 시간: 32ms

A, B, C = map(int, input().split())

def square(a, b, c):
    if b == 0:
        return 1

    half = square(a, b//2, c)

    if b % 2 == 0:
        return (half * half) % c
    else:
        return (half * half * a) % c

print(square(A, B, C))

먼저 곱셈을 처리할 함수 square()을 만들어준다.

 

b를 반으로 쪼갠 값을 half로 할당한 뒤,

b가 짝수라면 그대로 half * half를,

홀수라면 a * half * half를 반환한다. (물론 c로 나머지값 처리를 해줘야 한다.)

 

A, B = 2, 4 를 예시로 들어보자 👇

square(2, 4, c) (b = 4 짝수이므로 그대로 b//2)
= square(2, 2, c) * square(2, 2, c)
= square(2, 1, c) * square(2, 1, c) * square(2, 1, c) * square(2, 1, c)
이제 b는 1인 상태다.
여기서 b//2 = 0 이므로 half는 1, 그리고 b가 홀수이므로 else문으로 넘어가서 1 * 1 * 2 를 반환하게 된다.
즉 square(2, 1, c) = 2가 되는것이다.