포스트

[python] 백준 1629 - 곱셈

백준 1629 - 곱셈 [SILVER 1]


한 줄에 2^31 이내의 자연수가 세 개 주어진다.

순서대로, A, B, C 라고 할 때, A를 B번 곱한 수를 C로 나눈 나머지를 출력하면 된다.

당연하지만,

1
print((A**B)%C)

로는 절대 풀 수 없다!

A^B는 최대 (2^31)^(2^31) 라는 끔찍한 경우가 주어진다…

(2^31) ^ 1000 정도만 가도 python에서는 출력을 거부한다.

내가 컴퓨터라도 그 수를 메모리에 꾸역꾸역 넣는 것도, 그걸 연산하는 것도 역겨울 것 같다.

DP?

처음에는 DP로도 풀 수 있지 않을까 했다.

A를 차례대로 거듭제곱 해가면서 C로 나눈 나머지를 저장하고,

다시 동일한 패턴이 보이면 순환을 탈출하고

해당 패턴의 길이로 B를 나눈 뒤 나머지를 패턴의 인덱스로 쓰면

거듭 제곱 하는 수를 줄일 수 있을 것이다!

이건 숫자 제한이 2^16 정도였다면 가능했을지도 모르겠다.

근데 그럼 그냥 (A**B)%C를 해도 된다

수학 문제?

정답을 아무리해도 모르겠어서 찾아봤다.

분할 정복, DAC(Divide and Conquer)를 활용하는 수학 문제라고 한다.

b = x*y 일 때, a^b(a^x)^y라는 지수 법칙을 활용하자.

2 ** 82 * 2 * 2... 이런 식으로 7번 계산을 하게 되지만,

(2 ** 4) ** 22 * 2 * 2 * 2를 계산하여 16으로 만든 뒤,

16 * 16을 하므로 총 5번의 계산을 진행한다.

다시 (((2 ** 2) ** 2 ) ** 2) 로 나누면?

2 * 24를 만들고 다시 4*416을 만든 뒤 16 * 16으로 256을 만든다.

3번의 계산을 진행한 것이다.

이렇게 7번의 연산을 3번으로,

시간 복잡도로 따지면 O(n)을 대략 O(logn)으로 낮추는 게 가능한 것이다!

그래서 지수 법칙을 어떻게 사용할까?

처음에 생각한 건, while문을 통해 지수(b)를 소인수분해 해서 a**b를 최대한 빠르게 돌리는 것이었다.

다만, 이 경우 소수가 상당히 커질 수 있으므로 ((2 ** 31) ** 0.5 이내의 모든 소수)

소인수분해보다는 b를 2로 나눠, b가 1이 됐을 때 에서 a를 반환하고,

짝수일 경우 (b//2) ** 2, 홀수일 경우 ((b//2) ** 2) * a를 반환하는 함수로 재귀시키는 게 낫겠다 싶었다.

그렇게 최종적으로 반환된 값을 c로 나누면?!

1
2
3
4
5
6
7
8
9
10
11
12
a, b, c = map(int, input().split())

def fun(a, b):
    
    if b == 1:
        return a
    elif not b % 2:
        return fun(a, b//2) ** 2
    else:
        return (fun(a, b//2) ** 2) * a
    
print(fun(a,b) % c)

다만, a를 b만큼 거듭제곱하는 것은 빠를지 몰라도, 앞서 언급했듯 수가 지나치게 커지기 때문에 딱히 의미가 없다…

그럼 여기서 뭘 해야할까…

모듈러 연산의 분배법칙?

곱하고, 나누고, 나머지로 이것저것하는 암호학에서는 굉장히 중요한 개념이라고 한다.

연산의 횟수는 분할 정복으로, 연산할 객체의 크기는 모듈러 분배 법칙으로 줄이는 것이다.

여러 법칙이 있으나, 곱셈의 나머지 연산 분배 법칙을 활용하는 게 맞아 보였다.

(A×B)modC=((AmodC)×(BmodC))modC

즉,

(A×A)modC=A2modC (AmodC×AmodC)modC=(AmodC)2modC

로써, 거듭제곱 꼴로 만들어 지수법칙과 버무릴 수 있는 것이다.

A=5,C=3, A2modC=25mod3=1 (AmodC)2modC=4mod3=1

위와 같이 모듈러 분배법칙을 통해 연산할 경우 연산할 값의 크기를 확연히 줄일 수 있다!

정답 코드

이전에 만든 식을 활용해서,

b가 2로 나누어 재귀시키고 1에 도달할 경우 a % c를 반환한다.

한 번 올라가 b가 2(또는 3)가 되었을 때, a % c를 거듭제곱(b가 홀수인 경우 a를 곱해 지수를 맞춰준다)한 것을 다시 c로 나누면 된다.

조금 뇌정지가 왔던 부분은 b가 홀수가 되는 경우였는데,

그냥 a를 넣어도 되는 건가? 생각하던 중,

분배 법칙을 역으로 적용하면 된다는 걸 깨닫고 금방 이해했다…

b가 3인 경우,

a(amodc)2modc=a((amodc)×(amodc))modc=a(a×a)modc=a3modc

가 된다!

b를 5로 할 경우,

a((amodc)2×(amodc)2)modc=a(a2×a2)modc=a5modc

로 표현이 가능하다.

법칙을 역으로 쓸 방법을 떠올리지 못해 오랜 시간 머리를 싸매고 있었다…

1
2
3
4
5
6
7
8
9
10
11
def dac(a, b, c):
    
    if b == 1:
        return a % c
    mod = dac(a, b//2, c)
    elif not b % 2:
        return (mod * mod) % c
    else:
        return ((mod * mod) * a) % c
    
print(dac(a,b,c))

반전

그리고 놀랍게도 Python은 무려 기본 함수로 이 기능을 제공한다!!!!

모듈 불러오기조차 필요 없다…

1
2
3
4
5
pow(a, b, c)

# 백준 숏코딩 용

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

이 코드는 문제의 코드와 똑같은 기능을 한다.

암호화 관련된 연산에서는 굉장히 자주 쓰인다고 하니, 참고로 알아두자…

결과는 다음과 같다.

메모리시간코드길이
31120kb40ms37B
Algorithm
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.