[백준] 1629번 분할정복 알고리즘

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

# BOJ_1629

# 입력
a, b, c = map(int, input().split())
# result = (a ** b) % c
result = 1
for i in range(b):
    result *= a
result %= c
print(result)

역시 실버1가 이렇게 간단할리가

 

 

분할정복 알고리즘 순서

1. 분할 

해결할 문제를 시간복잡도를 낮추기 위해서

여러 개의 작은 부분 문제들로 분할한다.

2. 정복

나눈 작은 문제들을 각각 해결한다.

3. 통합

필요 시 해결된 해답을 모은다

 

# a를 n(= b)번 곱한다고 할 때
def recurisive_power(a, n):
    if n == 1:
        return a
    if n % 2 == 0:
        y = recurisive_power(a, n/2)
        return y * y
    else:
        y = recurisive_power(a, (n - 1)/2)
        return y * y


# 입력
a, b, c = map(int, input().split())
n = b
result = recurisive_power(a, n)
print(result % c)

잉.. 이렇게 했는데도 시간초과가 나온다.

 

 

# BOJ_1629
import sys
input = sys.stdin.readline
# a를 n(= b)번 곱한다고 할 때
def recurisive_power(a, n):
    if n == 1:
        return a % c
    # n이 짝수 이면
    if n % 2 == 0:
        y = recurisive_power(a, n//2)
        return (y * y) % c
    # n이 홀수 이면 n//2이니까 a를 한번 더 곱해준다.
    else:
        y = recurisive_power(a, n//2)
        return (y * y * a) % c


# 입력
a, b, c = map(int, input().split())
print(recurisive_power(a, b))

....

 

참조: https://m.blog.naver.com/sunbi5252/221977857377