[Python] S1_1629_곱셈 ✖

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

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제

😥 이 문제를 처음 보았을 때 쉽다라고 느낄 수도 있겠지만... 숫자가 굉장히 커질 때 이를 어떻게 처리해야하는가가 관건이었다. 결국에는 수학적인 개념이 필요하다는 것을 알게 되었다.

1. 지수 법칙

• 2^32는 2^16 X 2^16으로 나타낼 수 있다.
• 2^5는 2^2 X 2^2 X 2로 나타낼 수 있다.
• 이런 식으로 지수가 짝수라면 2로 나누어서 반복하고, 홀수라면 2를 나눈 후에 한 번 곱해줌으로써 지수를 맞춰준다.

2. 분배법칙

• 나머지를 구할 때도 분배법칙을 이용할 수 있다.

코드

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

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

1. 지수가 짝수이면 b//2로 다시 함수를 호출, ^2를 해주며 지수를 맞춘다. 만약 홀수라면, a도 한 번 곱해줌으로써 지수를 맞춰준다.

• 짝수인 경우: 2^10 = (2^5)^2
• 홀수인 경우: 2^5 = (2^2)^2 X 2

2. 이런 식으로 지수(b)를 계속해서 2로 나누어 주다가, 1이 나오게 되면 a % c 를 리턴하고 순차적으로 계산을 진행한다.

🤔 %c를 항상 붙여주는 이유?

• 분할을 한 뒤에 곱하기를 해주어도, 계산해야 하는 숫자가 너무 크기 때문에 나머지로 계속해서 만들면서 진행해주어야 한다.

• 여기서 두 번째 경우를 활용하는 것이다!

느낀 점 & 배운 점

1. 이해하는 데 꽤나 오래 걸린 문제이다. 지수 법칙과 분배 법칙에 대해서 잘 알아두면 나중에도 효율적으로 계산을 하는 데 유용하게 쓸 수 있을 것 같다!

2. 역시 알고리즘 문제를 풀 때 수학적인 지식이 필요한 것 같다.. 기본적인 공식들은 알아두어야겠다.