[BOJ] 1629. 곱셈

Python3

문제

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

키워드

• 수학
• 분할 정복을 이용한 거듭제곱

문제 풀이

문제 요구사항

자연수 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 프로그램
(A, B, C는 모두 2,147,483,647 이하의 자연수)
=> 얘네 곱하면 9000만 이상 나온다 .. 시간 초과되지 않아야 하는 문제

변수 및 함수 설명

• a, b, c: 자연수(a를 b번 곱해 c로 나눈 나머지 출력)
• dac(): 분할과 정복으로 계산하는 함수

풀이

지수 법칙

분배 법칙
$(a \times b)$ % $c$ = $(a$ % $c) \times (b$ % $c)$

즉, $10^{32}$은 $(10^{16})^2$으로도 계산할 수 있다. 연산 과정이 32번에서 17번(16번 곱한 것을 서로 곱함)으로 줄고, $((10^{8})^2)^2$는 10번으로 줄어든다. 계속 하다 보면 연산 횟수가 더 작아져 빠른 연산 수행이 가능해진다.

Divide and Conquer 함수의 매개변수는 a, b, c이다.
만약 b가 1이라면 $(a**1)$ % $c$ 즉 $a$ % $c$이다.
b가 짝수이면, dac에 a, b//2, c를 넣고 함수 결과값에 2를 곱해준다.
b가 홀수이면, dac에 a, b//2, c를 넣고 함수 결과값에 2를 곱하고 a를 한번 더 곱해준다.

최종 코드

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

def dac(a, b, c):
    if b == 1:
        return a % c
    elif b % 2 == 0:
        return (dac(a, b // 2, c) ** 2) % c
    else:
        return ((dac(a, b // 2, c) ** 2) * a) % c

print(dac(a, b, c))

피드백

분할과 정복. . 어렵다.. 정복하는 그날까지 ..