[백준1629&파이썬] 파이썬을 이용해 빠른 거듭제곱 구하기, Fast Computing Power

# 문제

백준 1629 곱셈 파이썬 풀이

1629번: 곱셈

# 코드

import sys

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

# A를 B번곱한수를 C로 나눈값
# O(logN)을 가지는 곱셈법을 사용해서 구해야 한다.

def power(a,b) :
  if b == 0 :
    return 1
  if b % 2 == 0 : # 짝수일때
    temp = b//2
    result = power(a,temp) % C
    return result*result
  else : # 홀수 일때
    temp = b//2
    result = power(a,temp) % C
    return result*result*a

print(power(A,B) % C)

## 파이썬에서 틀리는 풀이

import sys

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

# A를 B번곱한수를 C로 나눈값
# O(logN)을 가지는 곱셈법을 사용해서 구해야 한다.

def power(a,b) :
  if b == 0 :
    return 1
  if b % 2 == 0 : # 짝수일때
    temp = b//2
    result = power(a,temp)
    return result*result
  else : # 홀수 일때
    temp = b//2
    result = power(a,temp)
    return result*result*a

print(power(A,B) % C)

 

# 풀이

• 알고리즘 수업시간에 다뤘었던 문제이다. 기본 거듭제곱은 O(N)의 시간복잡도를 가진다.
• 제곱을 할때 제곱을 N번하는 것이 아닌 그것의 제곱의 꼴로 다시 풀어내는 방법을 이용한다면 O(logN)의 시간복잡도를 가질 수 있다.
• 재귀를 이용하여 분할정복을 한다.
• 종료조건에 유의하자
• 추가적으로 파이썬에서는 매우긴 숫자들도 지원한다. 대신 그 곱셈들의 곱을 할 경우 숫자가 매우 커져 시간초과가 발생할 수 있다.
• 재귀가 한바퀴 돌고 분해된 작은것에 대한 제곱이 이루어질때마다 % C의 모듈러 연산을 해줌으로써 수를 작게 떨어뜨려 큰수의 곱셈 자체에서 오는 시간을 아낄 수 있다.
• 모듈러는 각 재귀단계에서 해주지 않으면 시간초과가 난다.

 

# 참고

글 읽기 - 반복문을 통한 logN 풀이가 왜 통과되지 않는지 알고 싶습니다!