[백준] #1629 곱셈(python)

📌문제

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

입력

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

출력

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

예제 입력

10 11 12

예제 출력

4

백준 1629번 문제

💡Idea

입력되는 수의 범위만 봐도 그대로 구현하면 안될 것 같은 느낌이 폴폴 나는 문제입니다🤨

이 문제는 Divide and Conquer로 접근해야 풀리는 문제입니다.

그 뿐만 아니라, 지수 법칙과 나머지 연산에 대한 선행 지식까지 있어야 해결할 수 있어 생각보다 많은 것들을 고려해야 했던 문제입니다.

Divide and Conquer

분할 정복 연산(Divide and Conquer)는 그대로는 해결할 수 없는 문제를, 작은 문제로 분할하여 좀 더 쉽게 해결한 뒤 다시 합치는 기법을 말합니다.
퀵 정렬 및 합병 정렬이 분할 정복 알고리즘을 사용하는 대표적인 알고리즘이라고 할 수 있습니다.

지수 법칙

$a\neq0, \;m,n$은 자연수일 때,

• $a^m \times a^n = a^{m+n}$
• 따라서 $b$가 짝수인 경우, $a^b = a^{b/2} \times a^{b/2}$
• $b$가 홀수인 경우, $a^b = a^{b//2} \times a^{b//2} \times a^1$

나머지 연산

$(a \times b)\;mod\;c = (a\;mod\;c \times b\;mod\;c) \;mod \;c$

💻코드

• ⏰ 시간 : 72 ms / 메모리 : 30840 KB

import sys
input = sys.stdin.readline

A, B, C = map(int, input().split())

def DAC(a, b, c) :
    if b == 1 : return a % c # 제곱되어지는 수 b가 1인 경우
    elif b % 2 == 0: # b가 짝수인 경우 
        return (DAC(a, b/2, c) ** 2) % c
    else: # b가 홀수인 경우
        return ((DAC(a, b//2, c) ** 2) * a) % c

print(DAC(A, B, C))

📝코드 설명

지수 법칙과 나머지 연산에 대한 규칙을 적용하여 해결한 코드입니다.
b가 짝수인지, 홀수인지에 따라서 위의 지수 법칙을 다르게 적용해줍니다.
그리고, 마지막에만 c로 나누는 나머지 연산을 하면 a ** b 연산 과정에서 숫자가 굉장히 커질 수 있기 때문에, 모든 과정에서 %c 연산을 해줍니다.

⏰시간복잡도

• 단순하게 a를 b번 곱하는 경우 : $O(n)$
• 분할정복을 사용하는 경우 : $O(logn)$

👇 지수 법칙과 나머지 연산 적용에 따른 실행 시간 비교(위의 코드와 같이 작성하지 않으면, 시간 초과가 발생합니다.)

import sys
import time
input = sys.stdin.readline

A, B, C = map(int, input().split())

def DAC3(a, b, c):
    return (a ** b) % c


def DAC2(a, b) :
    if b == 1 : return a
    elif b % 2 == 0:
        return (DAC2(a, b/2) ** 2)
    else:
        return ((DAC2(a, b//2) ** 2) * a)


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


start = time.process_time()
print("정답 : ",DAC3(A, B, C))
print("수식을 그대로 실행한 경우 걸리는 시간 : ",time.process_time() - start)


start = time.process_time()
print("정답 : ",DAC2(A, B) % C)
print("지수 법칙만을 고려하여 실행한 경우 걸리는 시간 : ", time.process_time() - start)

start = time.process_time()
print("정답 : ", DAC(A, B, C))
print("지수 법칙과 나머지 연산을 고려하여 실행한 경우 걸리는 시간 : ", time.process_time() - start)

Reference

[백준] 1629번. 곱셈