백준 1629번: 곱셈 (Python)

1629번: 곱셈

# 정답코드

import sys
sys.stdin.readline

def conquest_num(num:int, index:int, C:int)->int:
    if index == 1:
        return num % C
    else:
        halfindex = index//2
        if index % 2 == 0:
            return conquest_num(num, halfindex, C) ** 2 % C
        else:
            return conquest_num(num, halfindex, C) ** 2 * num % C
        
A, B, C = map(int, input().split())
print(conquest_num(A%C, B, C) % C)

---

풀이

분할정복? 단어가 어려운건 아니다. 그냥 한번에 계산하기 어려운 문제를 나눠서 푼다는 뜻이니 편하게 생각하면서 들어가보자. 파이썬의 제곱(**, pow())의 시간복잡도는 O(n)이다. 그리고 파이썬은 무한대의 정수 범위를 지원하여 매우 큰 정수를 계산할 수 있지만 그만큼 계산속도가 떨어지게 된다.

import sys
sys.stdin.readline

def conquest_num(num:int, index:int, C:int)->int:
    if index == 1:
        return num 
    else:
        halfindex = index//2
        if index % 2 == 0:
            return conquest_num(num, halfindex, C) ** 2 
        else:
            return conquest_num(num, halfindex, C) ** 2 * num 
        
A, B, C = map(int, input().split())
print(conquest_num(A, B, C) % C)

이 코드는 낮은 수를 적용했을때는 정상적으로 돌아간다. 하지만 A,B가 2^31-1 이라고 가정했을때, 

한번의 제곱계산이라도 문제풀이시간인 0.5초를 바로 넘어버린다. 그러므로 A에다가 미리 C를 나눠주면 최대한 제곱연산에 대한 부담을 덜어줄 수 있다.

???: B가 2^31-1이면 어떡해요?

라고 질문하면 알려주는게 인지상정. (※ 한번 생각해보세요)

Q. 우리는 재귀를 왜 쓰는가?

A. 시간을 줄이기 위해

왜 쓰는지는 아래 써놓겠다.

원래의 O(n)의 시간복잡도를 O(logn)으로 바꿀 수 있다. 고로 아무리 많이 돌아봐야 31번보다 적게돌아서 시간복잡도 걱정을 안해도 된다!