[백준] 1629 : 곱셈

문제

풀이

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

def power(a, b, c):
    result = 1
    while b > 0:
        if b % 2 != 0: # 거듭제곱 해줘야 하는 지수가 홀수이면 a를 한 번 더 곱해줌
            result = (result * a) % c
        a = (a * a) % c # a를 계속 2개씩 b//2 번 곱해주면 a**b가 됨
        b = b // 2
    return result

print(power(a, b, c))

22.05.13 다시 풀어보기

풀이

import sys
input = sys.stdin.readline

a, b, c= map(int, input().split())

def sol(n):
    if n == 1:
        return a % c
    else:
        tmp = sol(n//2)
        if n % 2 == 0:
            return (tmp * tmp) % c
        else:
            return (tmp * tmp * a) % c

print(sol(b))

n == 1에서 리턴을 하는 이유

n이 1일 때부터 하나씩 depth를 올라오기 위해서다.
tmp에 그 아래 depth에서 리턴해준 가장 작은 단위의 값이 저장되고, n은 그 전 depth인 2로 올라오게 된다.
n이 2일 때 가장 작은 단위를 가지고 계산해줄 수 있다.
그 이후로 n이 5일 때도 리턴해준 값이 tmp에 저장되어 계속 재귀를 돌던 값을 tmp 변수에 넣어서 계산해줄 수 있다.

재귀 구조 정리