[BAEKJOON] 1629 곱셈 - Python

문제 요약

• 알고리즘 분류: 재귀호출, 분할정복
• 난이도: Silver1
• 문제내용:
  • A 를 B 번 곱해서 C로 나눠서 출력한다.
• 사이트 주소: https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

문제풀이

  위 문제는 아래처럼 pow 함수 사용하거나 제곱으로 연산하거나 for문으로 사용하면 시간 초과가 나올것이다.

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

# 그냥 제곱 연산으로 사용할 경우
result = A ** B % C

# for 문으로 사용할 경우
result = 1
for i in range(B):
	result *= A
    
# pow 함수 사용할 경우
from math import pow
result = pow(A, B)

 

접근방법

 재귀로 분할 해서 가져오면  O(logN)시간을 가져올수가 있다. 아래의 그림을 보면 이해 할수가 있다.'

A 제곱 B를 A 제곱 B/2 곱하기 2번하면 된다. 

A 제곱 B/2도 A제곱 B/4 곱하기 2번하면된다.

하지만 B에서 2 로 나뉘어  나머지가 1인 경우도 생각해야한다.  그럴경우에는 아래와 같이 A를 한번 더 곱해주면된다.

정리 한다면 아래와 같이 정의 할수가 있다.

재귀 함수 적용 법

1. 파라미터 값이 1일때는 A % C 로 리턴한다.
2. 파라미터 값이 2이상인 경우 파라미터값을 2로 나눠서 함수 재호출 해서 값을 가져온다.
3. 홀수 일때 재호출한 값을 제곱해서 A를 한번 더 곱한다음에 C 나머지 구한다.
4.  짝수 일때 재호출한 값을 제곱해서 C 나머지 구한다.

코드

Python

def pow(n):
    if n == 1:
        return A % C
    else:
        result = pow(n // 2)
        if n % 2 == 1:
            return (result * result * A) % C
        else:
            return (result * result) % C

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

print(pow(B))