파이썬 알고리즘 215번 | [백준 1629번] 곱셈 - 분할 정복을 이용한 거듭제곱

215. 곱셈

1) 어떤 전략(알고리즘)으로 해결?

• 분할 정복

2) 코딩 설명

수학
분할 정복을 이용한 거듭제곱
을 사용하는 문제

• 따라서 계속 b를 나눠주면 되는 것, 그것을 재귀함수로 구현하는 것
  • 이때 b가 홀수면 a^(b//2) a^(b//2) a
  • b가 짝수라면 a^(b//2) * a^(b//2)
    가 곱해지기 때문에

<내 풀이>

import sys
a,b,c = map(int, sys.stdin.readline().rstrip().split())

def remainder_thr(a,b,c) :
    # b가 1이 되면 이젠 
    if b==1 : return a%c 
    
    else : 
        target =remainder_thr(a, b//2, c)
        if b%2==1 : # 홀수라면
            return (target * target * a) %c
        else : return (target * target) %c

print(remainder_thr(a,b,c))

<내 틀렸던 풀이, 문제점>

시시시시간초과 (1)

import sys
a,b,c = map(int, sys.stdin.readline().rstrip().split())
res=1
for i in range(b) :
    res*=a
print(res%c)

시시시시시시시간초과 (2)

import sys
a,b,c = map(int, sys.stdin.readline().rstrip().split())
res=a**b

print(res%c)

시시시시시시시시간초과 (3)

import sys
a,b,c = map(int, sys.stdin.readline().rstrip().split())
cnt=1; res=1

def mull(p, a) :
    return p*a

while cnt<=b:
    res=mull(res, a)
    cnt+=1

print(res%c)

A, B, C는 모두 2,147,483,647 이하의 자연수, so 반복문으로는 절대 풀수없다고 한다!

출처 : https://tmdrl5779.tistory.com/114

<반성 점>

<배운 점>