[백준 1629] 곱셈 - python (solved.ac - 실버 1)

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

1629번: 곱셈

풀이

문제를 보았을때 알수있는 힌트

문제를 보면 단순해 보이지만 곱한수를 반복하다보면 시간 초과가 나는 문제이다.

이때 단순하게 나머지인 C의 길이만큼만 계산하면 해결하지 않을까 생각을 하며 풀었지만 시간 초과가 나오며 다른 사람들의 힌트를 얻어 문제를 해결하였다.

분할정복을 이용한 거듭제곱으로 재귀함수를 통해 곱셈을 줄여서 계산을 하면 O(n)을 O(nlogn)으로 바꿀수있어서 문제를 해결할수있다.

이번에 분할정복 관련해서는 알고리즘에 작성하며 나중에 비슷한 문제가 나오면 무조건 맞춰야겠다는 생각을 가진다.

 

import sys
# 제곱을 풀때는 분할정복을 알고있자!
def Recursive_Power(C,n):
    if n ==1:
        return C%c
    else:
        y = Recursive_Power(C,n//2)
    if n % 2==0:
        return y*y % c
    else:
        return y*y*C % c

input = sys.stdin.readline

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

result = Recursive_Power(a,b)

print(result)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1629.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리