[Python] 백준 1629 곱셈

 

문제 분석

• 자연수 A를 B번 곱한 수를 알고 싶다.
• but 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하라

 

코드 설계

• a,b,c는 20억 미만의 수
• 시간 제한 0.5초

 

정답 코드

1차 -실패 (런타임 에러)

재귀

import sys
input = sys.stdin.read

def mul(num, times, cnt) :
    if times == cnt :
        return num
    else :
        return num * mul(num, times, cnt+1)

a,b,c = map(int, input().split())
print(mul(a,b,1) % c)

디버깅하면 답은 구하는데 시간도 오래걸리고 런타임 에러

** by chatGPT

mul ( a,b,1 ) 호출 시, mul 함수는 총 b-1 번 재귀 호출됨
따라서 O(b)의 시간복잡도를 가짐

실행 시간은 0.5초
1초에 연산횟수 1억번이라고 했을 때 5000번의 연산정도만 할 수 있는데 문제에서 b는 20억까지 될 수 있다.
즉, b가 너무 크면 재귀 호출이 너무 깊어지고 실행 속도가 느려진다.

이를 개선하기 위해 분할 정복을 활용한 빠른 거듭 제곱 (Exponentiation by Squaring)

시간복잡도 : O(b) → O(log b)

import sys
input = sys.stdin.read

def mul(a,b,c) :
    if b == 0 :
        return 1
    half = mul(a, b//2, c)
    half = (half * half) % c
    return (half * a) % c if b % 2 else half

a,b,c = map(int, input().split())
print(mul(a,b,c))