[백준 알고리즘] - 곱셈 (1629번) with Python

📎 간략한 문제 정리

• 자연수 A를 B번 곱한 수를 계산합니다. 즉, A의 B제곱을 계산하는데 그 결과를 C로 나눈 나머지를 출력합니다.

📈 문제 분석

• A, B, C는 2,147,483,647 이하의 자연수입니다. 2,147,483,647(8번째 메르센 소수)는 2^31 - 1로 C언어 기준 정수자료형 최대치입니다(양의 정수 기준).

🙋‍♂️ 내가 처음 생각한 해결 방법

• 오버플로우 문제가 없다고 해도 A^B 연산이 끝난 뒤 C로 나누는 연산을 하면 속도 이슈가 발생할 수 밖에 없습니다. 그래서 각 연산의 중간에 C로 나누는 연산을 하는 구조로 작성해보겠습니다.
• 단순 반복으로는 연산 속도 이슈가 발생할 수 밖에 없습니다. 문제를 세분화하는 과정이 필요합니다(분할).

💻 풀이한 코드

from sys import stdin
input = stdin.readline
a, b, c = map(int, input().split())
def power(x, y, z):
    if y == 1:
        return x % z
    partial = (power(x, y // 2, z)) % z
    if y % 2 == 0:
        return (partial * partial) % z
    else:
        return ((partial) * (partial) * (x % z)) % z
print(power(a, b, c))

📝 해결 과정에서 만난 문제, 고민들

• 우선 분할을 생각할 필요가 있습니다. x^y를 계산할 때, y가 짝수인 경우와 홀수인 경우로 나눠서 생각해볼 수 있습니다. 예를 들어 10^10은 (10^5)(10^5)로 나눌 수 있습니다. 하지만 y가 홀수인 경우는 x를 한번 더 곱해주면 됩니다. 10의 11승은 (10^5)(10^5)*10으로 표현 가능합니다. 즉, 큰 수의 연산을 이분할하는 작업을 반복하여 기저조건, 즉 항이 1개일때까지 내려간 후 다시 곱해나가면서 올라옵니다.

• 단순히 분할 정복만으로는 시간 초과가 발생했습니다. 해결 방법은 partial이라는 부분 연산을 한번 연산하고 나머지는 그 결과값으로만 나타내는 것이었습니다. 같은 연산이라도 반복될 때는 새로운 연산을 하는 것과 마찬가지 이므로 큰 차이가 발생합니다. 이 partial 부분이 없다면 단순히 for문을 돌리는 것과 사실 연산하는 횟수는 같아지기 때문에 필수적인 부분이며 이 문제의 포인트였습니다.

• C언어에서 정수형은 4바이트로 이것은 32비트가 되므로 2^32개의 2진수를 표현할 수 있습니다. 가장 앞의 비트는 부호를 나타내므로 31자리이고, 양의 정수이므로 0을 빼서 2^31-1개의 자연수를 표현할 수 있습니다. 그러므로 기준이 최대일 때 단순 연산을 하면 반드시 오버플로우가 날 수 있습니다. 하지만 파이썬의 경우는 조금 다릅니다. 파이썬 버전2까지는 int와 long을 각각 제공했습니다. 이때의 int는 C언어의 int처럼 고정 정밀도 정수형이었고 long은 임의 정밀도 정수형이었습니다. 하지만 2.4버전부터 int가 충분하지 않으면 자동으로 long 타입으로 변경되는 구조가 되었으며 버전 3부터는 아예 int 단일형으로 통합되었습니다. 그래서 int형의 오버플로우가 발생할 일이 없습니다.

  • 메르센 수(Mersenne number): 2의 거듭제곱에서 1이 모자란 수 입니다.

  • 메르센 소수(Mersenne prime): 메르센 수 중 소수인 수입니다.

    3, 7, 31, 127, 819, 13107, 52428, 2147483647, 2305843009213693951...

• 임의 정밀도 정수형이란 무제한의 자릿수를 제공하는 정수형입니다. 정수를 숫자의 배열로 간주하여 자릿수의 단위를 쪼개어 배열 형태로 표현합니다. 기준은 2^30입니다.

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