💻 백준 1629: 곱셈

문제 소개 🧐

자연수 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 문제입니다. A, B, C는 매우 큰 자연수가 될 수 있습니다.

  • 예시: 10^11 % 12 = 4

입력 📝

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

출력 📤

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

제한 ❌

  • 시간: 0.5초
  • 메모리: 128MB

첫 번째 시도: 단순 구현 👊

Idea

문제에 제시된 그대로 A를 B번 곱한 후 C로 나누는 방식을 구현했다. 하지만 A와 B가 매우 크기 때문에 시간 초과나 메모리 초과가 발생할 것이다

Code

import sys

a, b, c = map(int, sys.stdin.readline().split())

# a^b를 직접 계산하면 수가 너무 커져서 시간 초과 발생
result = (a ** b) % c
print(result)

Result

  • 결과: 시간 초과
  • 원인 분석: a와 b가 최대 21억에 가까운 수이므로 a ** b를 직접 계산하는 순간 컴퓨터가 감당할 수 없는 어마어마한 숫자가 되어버린다. 당연히 제한 시간 0.5초를 훌쩍 넘기게 된다.

두 번째 시도: 분할 정복을 이용한 거듭제곱 ✨

Idea

거듭제곱을 효율적으로 계산하기 위해 분할 정복(Divide and Conquer) 기법을 사용했다. 지수 b를 절반으로 나누어 계산을 반복함으로써 시간 복잡도를 O(log b)로 줄일 수 있다.

Code

import sys

a, b, c = map(int, sys.stdin.readline().split())

def power(a, b, c):
    # 베이스 케이스: b가 1이면 a % c를 반환
    if b == 1:
        return a % c
    
    # b를 반으로 나누어 재귀적으로 호출
    res = power(a, b // 2, c)
    
    # b가 짝수인 경우
    if b % 2 == 0:
        return (res * res) % c
    # b가 홀수인 경우
    else:
        return (res * res * a) % c

result = power(a, b, c)
print(result)

Result

  • 결과: 정답! ✅
  • 핵심: 재귀 호출을 통해 지수를 절반씩 줄여나가며 O(log B)의 시간 복잡도로 문제를 해결했다. 각 단계에서 모듈러 연산을 적용하여 값의 크기를 c 미만으로 유지한 것이 핵심이었다.

개선할 부분 🤔

  • 이 문제의 핵심은 분할 정복을 이용한 거듭제곱과 모듈러 연산의 성질을 이해하고 적용하는 것이었다
  • 재귀 호출로 인한 오버헤드를 고려해, 반복문으로도 동일한 로직을 구현할 수 있을 것 같다
  • 분할 정복을 이용한 거듭제곱에 대해 확실히 공부해야겠다