백준 / 곱셈 / 1629번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 곱셈 / 1629번 (실버 1단계)

문제 사이트: https://www.acmicpc.net/problem/1629

 

문제 설명

 

---

 

나의 풀이

 

def solution(a, b, c):
    if b == 0:
        return 1
    elif b == 1:
        return a % c
    else:
        temp = solution(a, b // 2, c)
        temp = (temp * temp) % c
        if b % 2 == 0:
            return temp
        else:
            return (temp * a) % c

A, B, C = map(int, input().split())

print(solution(A, B, C))

---

※ 알아야 할 것

 

분활정복 알고리즘을 사용하여 문제를 풀면 쉽게 풀 수 있다.