[백준 1629][파이썬] 곱셈

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

1629번: 곱셈

이 문제를 해결하기 위해선 알아야하는 수학적 지식이 있다.

 

(a*b)%c=((a%c)*(b%c))%c

 

위 공식을 사용하면 이 문제를 분할 정복 방식으로 해결할 수 있다.

 

예를 들어 3을 12번 곱한 값을 7으로 나눈 나머지를 구한다면 

 

3을 6번 곱한 값을 7로 나눈 나머지를 구하고 이를 제곱하여 다시 7로 나누면 된다.

 

3을 6번 곱한 값을 7로 나눈 나머지는 3을 3번 곱한 값을 7으로 나눈 나머지를 구하고 이를 제곱하여 다시 7로 나누면 된다.

 

이렇게 하향식으로 접근하면 된다.

 

분할 정복 방식에 대해 익숙하지 않아서 처음에는 다음과 같은 코드를 작성했다.

import sys
input=sys.stdin.readline
a, b, c = map(int, input().split())
def solution(n, m):
    global c
    if m==1:
        return n%c
    return ((solution(n, m//2)%c)*(solution(n, m-m//2)%c))%c
print(solution(a, b))

문제를 분할하기 위해서 m을 나누었다.

 

그런데 위 방식은 분할을 했지만 사실상 의미가 없는 알고리즘이다.

 

b가 12라면 solution(a, 6)의 값을 구하고 한 번 더 solution(a, 6)의 값을 구하기 때문이다.

 

dp처럼 이전에 구한 값을 저장하고 다시 사용하는 것이 아니라서 같은 행위를 계속 반복하게 되는 것이다.

 

이를 해결하는 방법은 그냥 solution(a. 6)의 값을 구하고 이를 제곱한 후 c로 나누면 된다.

 

b가 11과 같은 홀수라면 어떨까? 위 공식을 잘 생각해보면 해결할 수 있다.

 

(((solution(m//2)**2)%c)*(a%c))%c

solution(a, 10)을 구하고 공식을 활용하여 11일때의 값을 구하면 된다.

import sys
input=sys.stdin.readline
a, b, c = map(int, input().split())
def solution(m):
    global c
    global a
    if m==1:
        return a%c
    if m%2==0:
        return (solution(m//2)**2)%c
    else:
        return (((solution(m//2)**2)%c)*(a%c))%c
print(solution(b))

이렇게 한다면 시간 복잡도를 log(n)까지 향상시킬 수 있다.