[백준] 1629번 : 곱셈 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 큰 수의 거듭제곱을 어떤 수로 나눈 나머지를 구하는 문제이다.

거듭제곱의 최종 결과를 가지고 나머지 연산을 하면 큰 숫자일 경우 그 계산이 쉽지 않다.

하여 거듭제곱을 전부 계산하기 전 작은 수일 때의 나머지 연산을 활용하여 최종 나머지 값을 구한다.

A * B % C의 연산을 나눠보면 ((A % C) * (B % C)) % C의 연산과 동일한 결과가 나오게 된다.

이를 활용해 거듭제곱의 나머지 연산을 구한다.

문제에 나와있는 예시를 활용해 보면, 10^11 % 12 연산은 ( (10^5 % 12) * (10^5 % 12) * (10 % 12) ) % 12의 연산으로도 볼 수 있다.

이를 더 작은 연산으로 나누면 ( ( ((10^2 % 12) * (10^2 % 12) * (10 % 2)) % 12 ) * ( ((10^2 % 12) * (10^2 % 12) * (10 % 2)) % 12 ) * (10 % 12) ) % 12의 연산으로도 볼 수 있다.

해당 연산의 과정을 분할 정복 알고리즘을 사용하여 나타낼 수 있고 이를 통해 문제를 해결할 수 있다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. A, B, C를 각각 입력받아 저장한다. A, B, C = map(int, sys.stdin.readline().split())
3. 거듭제곱 연산을 작은 거듭제곱으로 나누는 연산을 함수로 생성한다. def divide(b)
   1. 만약 거듭제곱의 지수가 1이면 더 이상 지수를 나눌 수 없으므로 그냥 A를 C로 나눈 나머지를 반환한다. if (b == 1): return A % C
   2. 반면에 아직 지수를 나눌 수 있으면 else
      1. 지수를 나누어 계산된 나머지 연산의 결과를 저장한다. result = divide(b // 2)
      2. 만약 지수가 짝수이면, 정확하게 두 개의 숫자로 나누어지므로 지수를 나누어 계산된 나머지 연산을 그대로 2번 곱해 그 결과를 다시 나머지 연산하여 반환한다. if (b % 2 == 0): return (result * result) % C
      3. 반면에 지수가 홀수이면, 정확하게 두 개의 숫자로 나누어질 수 없으므로 지수를 나누어 계산된 나머지 연산을 2번 곱하고 마지막에 거듭제곱이 되는 수를 한 번 더 곱해 그 결과를 나머지 연산하여 반환한다. else: return (result * result * A) % C
         
4. 거듭제곱 연산을 작은 거듭제곱으로 나누는 연산을 수행하고 반환된 최종 결과를 저장한다. answer = divide(B)
5. 구해진 최종 결과를 출력한다. print(answer)

3. 소스코드

import sys

A, B, C = map(int, sys.stdin.readline().split())

def divide(b):
    if (b == 1):
        return A % C
    else:
        result = divide(b // 2)
        if (b % 2 == 0):
            return (result * result) % C
        else:
            return (result * result * A) % C
    
answer = divide(B)
print(answer)