[Python] 백준 1629번 : 곱셈

www.acmicpc.net/problem/1629

 

푸는데 오래걸린 문제다

일단 이 문제의 핵심 포인트는 '시간제한' 이다.  사실 파이썬은 숫자가 long long 이상이어도 자동으로 더 많이 공간을 할당해서 수가 아무리 커지더라도 상관은 없다. 그치만 계산 시간때문에 overflow가 나지 않더라도 시간초과가 뜰 것이다. 

 

그래서 일반적인 방식으로 A^B를 계산할 수는 없는 것이다. 궁금해서 2147483647^2147483647 % 2147483647 을 넣어봤는데 10초가 지나도 답이 안뜨길래 아..이방식으로는 안되는구나 했다. (이 문제의 시간 제한은 언어 관련 없이 0.5초이다.)

 

ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

그래서 여기 나온 '빠른 모듈로 거듭제곱법'으로 풀었다. 

 

 

 

# import time
A, B, C = map(int, input().split())
# start = time.time()
arr = list(map(int, list(str(bin(B))[2:])))
bodyArr = [0 for _ in range(len(arr))]
for i, num in enumerate(arr):
    bodyArr[i] = num * int(2**(len(arr)-i-1))
modularArr = [0 for _ in range(len(arr))]
modularArr[-1] = A % C
val = 1
for i in range(0, len(arr)-1):
    # modular array 에 저장하기
    modularArr[len(arr)-i-2] = (modularArr[len(arr)-i-1] ** 2) % C
for i, k in enumerate(modularArr):
    if arr[i] != 0:
        val = val * k
print(val % C)
# print("time :", time.time() - start)

 

십진수를 이진수로 바꾸는 것, 그 수를 한글자씩 잘라서 배열에 넣는 것 등의 방식도 썼다. 

 

어려웠던건 이진수는 배열의 마지막 요소부터 계산해야 한다는 점? index에 접근할때 조금 헷깔렸다.