[BaekJoon] 백준 1629번 곱셈

[BaekJoon] 백준 1629번 곱셈

 

문제: www.acmicpc.net/problem/1629

 

내코드

 

• 이 문제는 일단 brute force 방식으로 접근하면 O(n) 시간 복잡도로 풀수 있지만 이 경우에 시간 초과가 남
• 분할 정복 방식으로 풀어야하는 문제: 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법
• 간단하게 생각하면 a^b mod c를 풀어야 하는 문제
• 여기서 b=2k+1 일때 a^b = (a^k)^2xa이고 b=2k일때 a^b = (a^k)^2임을 생각해보자
• 예를 들어 2의 16제곱이면 brute force 방식은 16번 계산해줘야하지만 분할 정복을 하면 2의 8제곱한 결과를 제곱해주면 된다. 즉, 2의 8제곱은 2의 4제곱의 제곱이고, 2의 4제곱은 2의 제곱의 제곱이므로 총 계산 횟수는 4번으로 계산 횟수가 훨씬 줄어든다.
• b=2k+1일때는 a를 한번더 곱해주기만 하면 된다.

 

def multiple(a, b):
    # b가 1이면 곱해줄 필요가 없으므로 a % C를 리턴
    if b == 1:
        return a % C
    else:
        # a^b를 구할때 (a^(b/2))^2에서 a^(b/2)를 먼저 계산해줘서 활용
        value = multiple(a, b // 2)
        # (a^(b/2))2을 할때, b가 짝수인 경우, b/2가 나머지 없이 나눠지므로 ( a^(b/2) * a^(b/2) ) / c를 해줌
        if b % 2 == 0:
            return value * value % C
        # (a^(b/2))2을 할때, b가 홀수인 경우, b/2가 나머지 1이게 나눠지므로 ( a^(b/2) * a^(b/2) * a ) / c를 해줌
        else:
            return value * value * a % C


if __name__ == "__main__":
    A, B, C = map(int, input().split())
    print(multiple(A, B))

 

참고

jjangsungwon.tistory.com/10