난이도 🥈1

📌코드

import sys
sys.setrecursionlimit(1500)

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


def mul(A, B):
    if B == 1:
        return A % C
    elif B % 2 == 0:
        return (mul(A, B//2)**2) % C
    else:
        return A*(mul(A, B//2)**2) % C


print(mul(A, B))

📌후기

분할 정복 이라는 카테고리를 알고 푸니 그래도 접근 방식은 쉬웠던 것 같다. 만약 실제 코딩 테스트에서 이런 문제가 나왔다면 체감상 더 어려웠을 것 같음.

접근

2^32 = 32번
(2^16)^2 = 17번
(2^8)^2)^2 = 10 번
(((2^4)^2)^2)^2 = 7번
((((2^2)^2)^2)^2)^2 = 5번

2 32개를 일일이 32번 곱하는 것 보다
덩어리? 들을 계속 만들어서 곱하면 계산 횟수를 많이 줄일 수 있다.

실수했던 부분

import sys
sys.setrecursionlimit(1500)

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


def mul(A, B):
    if B == 1:
        return A
    elif B % 2 == 0:
        return (mul(A, B//2)**2)
    else:
        return A*(mul(A, B//2)**2)


print(mul(A, B) % C)

처음 작성했을 때는 C를 바깥으로 빼면 시간초과가 났었다. 문제에도 나타나 있듯이 구하려는 수가 함수내부에서 매우 커져서 시간초과가 나는 것 같다.

📂분배법칙

( A + B ) % M = (( A % M ) + ( B % M )) % M

( A * B ) % M = (( A % M ) * ( B % M )) % M

( A - B ) % M = (( A % M ) - ( B % M )) % M