[CLASS 4]백준 1629번 - 곱셈

1629번 : 곱셈

 

아주 간단명료한 문제이다. 이 문제를 푸는데 있어서 파이썬의 pow함수를 사용한다면 그냥 날로 먹을수도 있다.

 

pow함수는 인자로 밑, 지수 [, 나누는 수]를 받는다. 그래서 pow(a,b,c)를 사용한다면 문제가 풀린다. 그것도 재귀함수로 푼 것보다 빠르게 작동한다...

 

그래도 공부하기위해 문제를 푸는 것이니 제대로 풀어야 한다.

 

내 코드:

def power(r):
    if not r:
        return 1
    elif r == 1:
        return a
    if r % 2:
        return power(r // 2)**2 * a % c
    else:
        return power(r // 2)**2 % c
a,b,c = map(int,input().split())
print(power(b) % c)

 

재귀가 들어가서 좀 머리가 아플 수도 있는데, 핵심적인 원리는

 

n^m 을 한다고 할 때, 그냥 n을 m번 곱한다면 O(n)의 시간 복잡도이고, 이는 이 문제에서 통과할 수 없는 시간 복잡도이다.

 

시간을 줄이기 위해서는 지수를 낮춰야 한다. 분할 정복을 이용한다면 한번씩 곱해서 -1씩 지수를 낮추는게 아니라, 지수를 /2 씩 줄일 수 있다.

 

간단히 생각하여 7^4 를 구한다고 할 때, 7*7*7*7 이 아닌 49*49 를 사용하는 방법이다.

 

이 방법을 사용한다면 지수를 2로 나누면서 연산하기 때문에 2^k = n -> O(log n)의 시간 복잡도로 문제를 해결할 수 있다.