[백준] #1629 곱셈 python

 

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

1629번: 곱셈

📕 설명 📕

Divide and Conquer.

 

그냥 풀었다가 큰 코 다친 문제.

 

시간초과가 계속 떴다.

 

그래서 풀이 방법을 바꿔보았다.

 

분할 정복으로 풀이했다.

 

🧑🏻‍💻 나의 풀이 🧑🏻‍💻

 

def Divide_and_Conquer(a, b):
    if b == 1:
        return a % C
    else:
        temp = Divide_and_Conquer(a, b // 2)
        if b % 2 == 0:
            return temp * temp % C
        else:
            return temp * temp * a % C


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

    result = Divide_and_Conquer(A, B)
    print(result)