[Silver I] 곱셈 - 1629 ( 분할 정복 )

[Silver I] 곱셈 - 1629

문제 링크

성능 요약

메모리: 113112 KB, 시간: 108 ms

분류

분할 정복을 이용한 거듭제곱(exponentiation_by_squaring), 수학(math)

문제 설명

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

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

-첫 풀이

코린이 특징 => 시간 초과가 날 것을 알면서도 해보기

 

-분할정복 풀이

import sys
input = sys.stdin.readline
a, b, c = map(int,input().split())
def conquer(num, squared):
  if squared == 1:
    return num % c
  elif squared % 2 == 0:
    recursive = conquer(num, squared/2)
    return recursive * recursive % c
  else:
    recursive = conquer(num, (squared-1)/2)
    return recursive * recursive * num % c

print(conquer(a,b))

분할정복으로 복잡도를 줄여야 통과가 되는 문제다.

분할정복은 동일한 수식을 반으로 계속 쪼개어서 나눈 문제들을 재귀 방식을 통해  각각 해결한다.

해당 문제처럼 같은 수를 제곱하는 것은 분할정복 문제들의 가장 베이스적인 문제인 것 같다.

출처 : https://m.blog.naver.com/sunbi5252/221977857377

분할정복의 기본 알고리즘을 가장 잘 설명한 그림이 있어 이것을 참고하면 이해하기가 더 쉬울 것 같다.

처음에 아무 생각없이 c로 나눈 나머지를 출력할 때만 해서 시간 초과가 났었는데, return한 값이 결국 계산한 값이므로, 출력문(print)에 c로 나눈 나머지를 구해야 할 게 아니라, return 할 때마다 c로 나눈 나머지를 구해야 한다.