백준 [1629. 곱셈] - python

☞ 문제 1629번 : 곱셈

1629번: 곱셈

☞ 풀이

♤ A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

♤ 곧이곧대로 알고리즘을 설계한다면, 런타임 에러를 직면하게 될 것이다.

      ♠ OverflowError : A를 B번 곱하여 정수에서 요구하는 범위를 벗어나는 결과값을 도출할 경우

      ♠ MemoryError : 주어진 128 MB 메모리 제한을 넘길 경우

      ♠ 시간 초과 : 주어진 0.5초 시간 제한을 넘길 경우

♤ 분할정복 알고리즘을 적용하여 문제의 알고리즘을 설계하자.

☞ study

▷ 분할정복(Divide and Conquer) 알고리즘

분할(Divide) - 문제를 2개 이상의 문제로 나눈다.

정복(Conquer) - 나눠진 문제가 여전히 분할 가능하면, Divide를 수행한다. 그렇지 않으면, 문제를 해결한다.

통합(Combine) - Conquer 한 문제들을 통합하여 원래 문제의 해답을 도출한다.

• 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하고, 다시 합병하여 최종 문제를 해결하는 알고리즘이다.
• 분할정복 알고리즘은 재귀함수로 많이 활용되고, 문제 알고리즘의 효율성을 향상시킬 수 있다.
• 시간복잡도는 O(log₂n)이다.

• 코드에서 Divide_Conquer(base, power, division) 함수를 살펴보자.
• base는 변수 a를 받는 매개변수이다.
• power은 변수 b를 받는 매겨변수로 power가 1인 경우, 주어진 문제를 더 이상 작은 문제로 분할할 수 없으므로 필요한 계산(division 사용)을 실행한다. power가 짝수인 경우, power를 2로 나누어 작은 문제로 분할한다. power가 홀수인 경우, (power - 1)한 값을 나누어 작은 문제로 분할한다. (이때 -1한 값은 필요한 계산때 추가적으로 넣어 계산한다.)
• division은 변수 c를 받는 매개변수로 문제를 계산하기 위해 필요한 요소이다.

▶ 참고 Divide and Conquer (분할정복)

▶ 참고 [파이썬 알고리즘] 4. 분할 정복

 

 

 

☞ 코드

import sys

# 분할정복 알고리즘 재귀함수
def Divide_Conquer(base, power, division):
    if power == 1:
        return base % division

    if power % 2 == 0:
        tmp = Divide_Conquer(base, power/2, division)
        return (tmp * tmp) % division

    else:
        tmp = Divide_Conquer(base, (power-1)/2, division)
        return (tmp * tmp * base) % division

# main
a,b,c = map(int,sys.stdin.readline().split()) 
print(Divide_Conquer(a,b,c))

 

☞ 결과

• 맞았습니다!! 
• 메모리 :  121220KB
• 시간 : 104 ms