[BOJ] 백준 1629. 곱셈, 분할정복과 거듭제곱

🥈 곱셈

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

곱셈

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

0.5 초 (추가 시간 없음)

128 MB

108788

30296

22110

26.824%

문제

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

입력

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

출력

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

예제 입력 1

10 11 12

예제 출력 1

4

💡 아이디어

분할정복에 대한 개념을 잡아야 문제를 풀 수 있는 것 같다.

분할 정복 Divide and Conquer

여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다.

대표적으로는 퀵소트나 병합정렬이 있다.

🔨

문제에서 필요로 하는 거듭제곱 또한 분할 정복 알고리즘을 활용하여 빠르게 계산이 가능하다.

임의의 수 C에 대하여 Cⁿ을 구할 때는 C를 n번 곱하므로 시간복잡도가 O(n)인 반면,

분할 정복을 활용하여 계산하면 O(logn)의 시간 복잡도로 계산이 가능하다.  🔨

분할 정복으로 거듭제곱을 계산하는 아이디어는 지수법칙을 활용한 다음과 같은 공식을 활용한다.

C의 n승에서 n이 짝수일 때 C^n = C^n/2 * C^n/2

C의 n승에서 n이 홀수일 때 C^n = C^n-1/2 * C^n-1/2 * C

✏️ 풀이

시간초과코드

# 거듭제곱구하기 A를 B번 곱하기
def power(A, B):
    if B == 1: #지수가 1
        return A
    else:
        tmp = power(A, B//2)
        if B%2 == 0:
            return tmp*tmp
        else:
            return tmp*tmp*A

import sys
input = sys.stdin.readline
ans = 0

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

ans = power(A,B)
print(ans%C)

정답 코드

재귀에 나머지 연산을 같이 넣어주니 시간초과가 해결되었다.

아래 거듭제곱을 구하는 공식이 처음엔 너무 어려웠다.

지수가 5라고 가정하면 5//2는 2이다

그러므로 C^2 * C^2 * C → C^1 * C^1 * C^1 * C^1 * C 이렇게 풀어진다.

이걸 생각하면서 재귀를 적용해준다

# 거듭제곱구하기 A를 B번 곱하기
def power(A, B, C):
    if B == 1: #지수가 1
        return A % C
    else:
        tmp = power(A, B//2, C) 
        if B%2 == 0: #짝수일떄 지수 식 **C^n/2 * C^n/2**
            return (tmp*tmp) % C 
        else: #홀수 지수 식  **C^n-1/2 * C^n-1/2 * C**
            return (tmp*tmp*A) % C

import sys
input = sys.stdin.readline

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

print(power(A,B,C))