[Python/코테] 백준 1629 곱셈

1629 곱셈

문제 및 조건 설명: https://www.acmicpc.net/problem/1629

알고리즘 설계

💡idea.

문제에서 주어진 대로 바로 a 곱셈을 b번 반복하면, 시간 초과 판정이 날 수 있다. (b가 최대 21억이기 때문)

수행해야 하는 연산은 곱셈 또는 나머지 연산으로 동일하므로 재귀함수를 사용할 수 있다.

$a^n * a^n = a^{2n}$이 힌트가 된다.

 

🎲step.

1. 함수 정의

a를 b번 곱해서 m으로 나눈 수를 출력한다. ($a^b$ mod m 계산) 

def POW(a, b, m)

 

 

2. base condition 

b = 1 일 때 종료

 

3. 재귀

$a^n * a^n = a^{2n}$을 힌트 삼아, 계속해서 지수를 이등분하여 제곱 연산량은 줄이면서 나머지를 구할 수 있다.

b가 짝수일 때 $a^{b/2}$ mod m 을 제곱한다. 

b가 홀수일 때 $a^{b/2}$ mod m 을 제곱한 뒤 a를 한 번 더 곱한다.

알고리즘 구현

a, b, c = map(int, input().split())


def pow(a, b, m):
    if b == 1:		# base case (종료 조건)
        return a % m

    val = pow(a, b//2, m)	# / 연산자는 항상 부동 소수점 결과를 반환하고, // 연산자는 항상 정수를 반환 
    val = val * val % m

    # b가 짝수일 때
    if b % 2 == 0:
        return val
    # b가 홀수일 때
    return val * a % m


print(pow(a, b, c))

b가 계속 절반으로 깎이기 때문에 $O(log b)$의 시간복잡도를 가진다.

나다어

• 귀납적인 사고를 하자! 점화식과 같은 패턴을 찾는다고 생각하면 될 듯.
      * 절차지향적 사고: pow(5, 14, 3) → pow(5, 7, 3) → pow(5, 3, 3) →... 와 같이 단계별로 생각하는 것
  ex) 1번 도미노가 쓰러진다.
        k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다.