백준 / 1629번 / 곱셈 / python 파이썬

 

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

 

 

처음 문제를 보고 쉬운 문제라고 생각하고 바로 풀었으나 

import sys
input = sys.stdin.readline

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

print((a ** b) % c)

 

바로 시간 초과가 났다. 

이 문제는 Divide and Conquer, 분할 정복의 원리를 사용해야 풀 수 있는 문제였다. 

 

분할 정복이란?

분할 정복 (Divide and Conquer)은 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다. 

 

분할 정복이 일반 재귀 호출과 다른 점은 문제를 한 조각과 전체로 나누는 대신, 비슷한 크기의 부분 문제로 나눈다는 점이다.

이미지 출처: https://gamedevlog.tistory.com/58

 

코드

분할 정복을 이용한 코드

import sys
input = sys.stdin.readline

def dac(a, b, c):
    if b == 1:
        return a % c

    tmp = dac(a, b // 2, c)
    print(tmp)
    
    if b % 2 == 1:
        return ((tmp * tmp) % c) * a % c
    else:
        return (tmp * tmp) % c

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

print(dac(a, b, c))