[백준][분할 정복] 1629. 곱셈(파이썬/Python)

<오답>

import sys
input = sys.stdin.readline

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

print((a**b)%c)

# 시간초과 당연하다 ^-^. 범위가 엄청 넓기 때문 이를 쪼개서 사용해야 한다.

 

<정답>

import sys
input = sys.stdin.readline

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

def dc(a,b):
    # 지수가 1일 경우엔 n^1은 n이기 때문에 그대로 값 반환
    if b == 1:
        return a % c
    else:    
        temp = dc(a,b//2) 
        
        # 지수가 홀수라면 n^2 * n^2 * n을 해주어야 하기에 이렇게 진행
        if b % 2 == 1:
            return temp * temp * a % c
        else:
            return temp * temp % c

print(dc(a,b))

Divide And Conquer 를 쪼개서 살펴보자면 이렇게 아래의 모양으로 쪼갤 수 있다. 

 

# degenerate case 

    # 지수가 1일 경우엔 n^1은 n이기 때문에 그대로 값 반환
    if b == 1:
        return a % c

# divide

temp = dc(a,b//2)

# conquer

        # 지수가 홀수라면 n^2 * n^2 * n을 해주어야 하기에 이렇게 진행
        if b % 2 == 1:
            return temp * temp * a % c
        else:
            return temp * temp % c