11.27 알고리즘 문제풀이

코테 연습

 

기타

첫 번째

https://www.acmicpc.net/problem/1629

1629번: 곱셈

import sys
input = lambda: sys.stdin.readline().rstrip()

def multiply(b):
    if b == 1:
        return A

    sub_result = multiply(b//2) % C
    result = sub_result ** 2
    return result*A if b % 2 == 1 else result

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

print(pow(*map(int,input().split())))

내 풀이와 다른 참고 풀이

 

풀이의 시작은

단순히 A를 B번 곱한다면(A ** B) 20억번이나 해야하잖아? 그럼 안되겠는데?

 

제곱수의 절반 제곱수는 서로 같다는 사실을 이용해서 위와 같이 재귀적으로 풀어낼 수 있다.

다만, 주의해야할 것은 값이 매우 클 수 있기 때문에(20억을 20억번 곱한다면)

이를 연산하는 것 자체가 오래걸릴 수 있다.

그래서 연산과정에서 나눗셈을 적용하면서 재귀 함수로 구현한다.

위와 같이 진행해도 같을 수 있는 것은 간단하게 증명할 수 있으니 직접해보자.

 

아래 다른 참고 풀이를 보면

pow라는 내장함수가 위 코드와 동일한 내용으로 작동하는 것같다.