[Python] 분할정복, 나머지 모듈러연산(합동식) 활용한 백준 1629번(곱셈) 문제 풀이

 

1. 백준 1629번(곱셈)

 

안녕하세요! FlyDuck_Dev🦢 입니다. 오늘은 백준 1629를 풀면서 겪었던 어려움과 문제 해결을 위해 이해한 합동식, 모듈러 연산에 대해 정리하는 포스팅을 작성해도록 하겠습니다. 

 

2. 기존 풀이

 

factorial을 짜듯이 재귀를 활용해서 문제를 풀면 되겠다고 생각해서 아래와 같이 코드를 작성하였습니다.

import sys
a, b, c = map(int, sys.stdin.readline().strip().split())

def power(a,n):
    if n <= 1:
        return a 
    else:
        return a * power(a, n-1)
    
aa = power(a, b)
print(aa)
print(aa%c)

수가 너무 커서 런타임 에러

 

문제는 단순히 A^B를 계산하는 재귀 함수를 구현하고, 이를 이용하여 A^B를 계산하고 C로 나눈 나머지를 출력하는 것을 요구하는 것으로 보이나 b의 값이 매우 클 경우, 시간 복잡도가 크기 때문에 합동의 거듭제곱 성질을 이용하여 빠르게 A^B를 계산하는 것이 핵심이었습니다.

결국 분할 정복 문제이며, 분할 정복해서 풀기 위해서 모듈러 연산의 성질에 대해서 알고 있어야 한다는 것을 알게 되었습니다.

 

3. 수의 합동과 모듈러(나머지, modulo)연산

 

(1) 수의 합동

대수학에서의 합동식이 있습니다.

도형 뿐만 아니라 수, 또는 식에서도 합동이 있습니다. (기하학에서 합동의 대상은 도형인데, 대수학에서 합동의 대상은 수)

합동은 완벽하게 일치하지 않아도 괜찮으나 필수 조건이 있습니다.

기하학에서 두 도형의 위치와 방향을 불문하고 각과 변만 같으면 합동이라고 합니다.

대수학에서 합동인 두 숫자는, 숫자의 실제 크기를 불문하고 어떤 수로 나누었을 때 나머지만 같으면 합동이라고 합니다.

 

​a를 m으로 나눈 나머지와 b를 m으로 나눈 나머지가 같으면 a와 b는 m에 대하여 합동이라고 표현합니다.

기호로는 a≡b (mod m) 이라고 표시합니다.

(mod modulo를 줄여서 쓴것으로, 나머지라는 뜻을 가진 기호입니다.)

예를 들어, 12와 18은 6으로 나누어떨어지기 때문에 12 ≡ 18 (mod 6) 이라고 표현할 수 있습니다.

 

예시

2 ≡ 2 (mod 3)

5 ≡ 2 (mod 3)

 

 

(2) 합동식의 기본 성질

 

​https://mathjk.tistory.com/3203

(수리논술) 합동식의 기본성질

여러가지 성질이 있는데, 백준 1629번을 풀기 위해서는 아래의 성질을 이해하면 됩니다.

특정 mod에 대하여 두 개의 합동 식을 아래로 곱하여도 합동이 됩니다.

 

예시 1

100 ≡ 1 (mod 3)   100을 3으로 나누면 나머지가 1이다. 1을 3으로 나누면 나머지가 1이다. [동일하게 나머지 1이므로 합동]

5 ≡ 2 (mod 3)      5를 3으로 나누면 나머지가 2이다. 2를 3으로 나누면 나머지가 2이다.    [동일하게 나머지 2이므로 합동]

500 ≡ 2 (mod 3)  500을 3으로 나누면 나머지가 2이다. 2를 3으로 나누면 나머지가 2이다.[동일하게 나머지 2이므로 합동]

100*5 =500, 1*2 =2

 

예시 2

48 ≡ 6 (mod 7)   48을 7로 나누면 나머지가 6이다. 6을 7로 나누면 나머지가 6이다.

26 ≡ 5 (mod 7)    26를 7으로 나누면 나머지가 5이다. 5를 7로 나누면 나머지가 5이다.

1248 ≡ 30 (mod 7)  1248을 7로 나누면 나머지가 2이다. 30을 7로 나누면 나머지가 2이다.[동일하게 나머지 2이므로 합동]

48*26 = 1248, 6*5 =30

 

-3- 합동식의 '거듭 제곱 성질'

위의 기본적인 합동식의 특성으로 뽑아낼 수 있는 합동식의 거듭제곱 성질은 다음과 같습니다.

• a ≡ b (mod m)일 때, a^n ≡ b^n (mod m)

예시 1

5 ≡ 2 (mod 3)   

5 ≡ 2 (mod 3)   

25 ≡ 4 (mod 3)

5의 제곱과 2의 제곱은 3으로 나누었을 때의 합동이다.

 

예시 2

5 ≡ 2 (mod 3)   

5 ≡ 2 (mod 3)

5 ≡ 2 (mod 3)   

125 ≡ 8 (mod 3)

5의 세제곱과 2의 세제곱은 3으로 나누었을 때의 합동이다.

 

4. 백준  1629 번에 적용

거듭 제곱은 아래와 같이 나누어서 계산할 수 있습니다.

A^11 = A^8 * A^2 * A^1

 

예시 2^6 = 2^3 * 2^2 * 2^1

 

백준문제는 한 문장으로 풀어말하면, A를 B번 곱한 수를 C로 나눈 나머지를 구하는 문제입니다.

따라서 A^B를 직접 계산하지 않고 A를 2의 거듭제곱 형태로 계속 분할하면서 계산할 수 있습니다.

 

예시

A^11 = A^8 * A^2 * A^1

윗줄은 아랫 줄과 같다

A^11 = (A^4 * A^4) * A^2 * A^1

윗줄은 아랫 줄과 같다

A^11 = ((A^2)^4) * A^2 * A^1

 

위와 같이 A를 분해하여 계산하면서 더 빠르게 A를 B번 곱한 수를 C로 나눈 나머지를 구하여 나가는 아이디어로 분할 정복하면서 풀어야 합니다.

 

5. 최종 정리와 코드

합동식이란 두 수의 차가 어떤 정수의 배인 두 수를 의미하며, a ≡ b (mod m)은 "a와 b를 m으로 나눈 나머지가 같다"는 의미입니다.

백준 1629번 문제는 합동식의 거듭제곱 성질 및 기본적인 거듭제곱 공식을 이해하여, 분할정복 기법을 적용하여 풀어야 합니다.

 

합동식의 거듭제곱 성질

a≡b (mod m) 일 때, a^n ≡ b^n (mod m)

 

기본적인 거듭제곱

a^m * a^n = a^(m+n)

(a^m)^n = a^(m*n)

 

A^4은 (A^2)^2

A^11 = (A^4 * A^4) * A^2 * A^1

= ((A^2)^4) * A^2 * A^1

import sys
a,b,c = map(int, sys.stdin.readline().split())
def divide_conquer(a,b,c):
    if b <= 1:
        return a % c
    temp = divide_conquer(a,b//2,c)
    if b % 2 ==0:
        return (temp * temp) % c
    else:
        return (temp * temp * a) % c


print(divide_conquer(a,b,c))

코드적으로 까다로운 부분은 짝수와 홀수 케이스를 분별하는 것입니다.

b가 짝수인 경우, temp * temp을 계산하여 반환합니다. 

b가 홀수인 경우, temp * temp * a을 계산하여 반환합니다.