[Baekjoon]백준 1629 곱셈(실버 1) - Python

문제설명

문제를 보면 아주 단순하다 첫번째 입력받은 숫자를 두번째 입력받은 숫자만큼 제곱하고, 세번째로 입력받은 숫자로

나누었을때의 나머지를 출력하면 된다 이 문제를 풀기위해 수학 공식의 일부를 사용하였는데,

예를 들어 (10 x 20) % 4의 경우 (10 % 4) x (20 % 4)와 동일하다는 점을 활용하여 코드를 작성하였다

num, square, div = map(int, input().split())

if num > div:
    num %= div
    
tmp = num
for _ in range(square):
    tmp = tmp * tmp % div
    
print(tmp)

분할정복 테마답게...시간초과가 발생한다 혹시나 했는데 역시나였다

그래서 이 숫자를 나누어 계산하되, 재귀함수를 이용하는 코드를 작성할 방법을 생각해보았다

함수에 숫자와 지수를 입력받고, 지수가 1이라면 그냥 나머지를 return한다

지수가 1보다 크다면 지수를 반으로 나눈 경우를 재귀함수의 인자로 전달하되,

지수가 2의 배수인 경우와 2의 배수가 아닌 경우로 나누어 return을 처리해주었다

만약 2의 배수가 아니라면 곱해지지 않는 수가 생기기때문에 return할 때 같이 전달하면 된다 

그리고 이 로직을 사용한 코드를 제출하면 정답임을 확인할 수 있다

num, square, div = map(int, input().split())

def sol(num, square):
    if square == 1:
        return num % div
    else:
        tmp = sol(num, square // 2)
        if square % 2 == 0:
            return (tmp * tmp) % div
        else:
            return (tmp * tmp * num) % div
    
print(sol(num, square))