백준 / 1629번 - 곱셈 (분할정복) / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 1629번 - 곱셈 (분할정복)  

문제 사이트: https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

128 MB

97802

26998

19716

26.655%

문제

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

입력

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

출력

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

예제 입력 1 복사

10 11 12

예제 출력 1 복사

4

 

 

---

처음에 바로 풀 수 있다고 생각했는데... 수가 커지면 시간초과가 나는 문제였다.

 

그래서 살짝 알고리즘 뭐써야하는지 봤는데 분할정복을 써야하는 것을 알게 되었다.

 

A, B, C는 모두 최대 2,147,483,647의 자연수가 입력될 수 있기 때문에

 

21억번을 직접 곱한다면 O(n)의 연산으로 시간초과가 나는 것이다.

 

이를 O(logN)으로 줄여줘야하는데, 이때 분할 정복을 쓴다.

 

- 분할정복 알고리즘 과정

1. a, b, c를 입력받는 함수 dac를 만든다.

2-1. 만약 b가 1이라면 (a**1)%c를 출력하는데, 어떤 수의 1승은 그 수 자신이기 때문에 b가 1이면 a%c를 return한다.

 

 

2-2. 만약 b가 짝수라면, dac 함수에 다시 넣는데, a의 b//2승을 한 뒤 해당 함수 자체에 2를 곱해주는 것이다.

       -> 예시) 2^32 = 2^16 * 2^16  = (2^16)^2            `지수법칙` 활용!

                         2^16 = 2^8 * 2^8

 

2-3. 만약 b가 홀수라면 a의 b//2승을 계산한 뒤 2를 곱하고 다시 a를 곱하여 a의 b승을 만들어 준다.

       -> 예시) 2^11 = 2^5* 2^5 * 2  = 2^(5+5+1)    = (2^5)^2*2    `지수법칙` 활용!

 

 

풀이

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

abc = list(map(int, input().split()))
print(dac(abc[0], abc[1], abc[2]))

 

---

※ 알아야 할 것

- 분할 정복을 이용해서 O(n) 인 식을 O(logN) 으로 만들어야한다