곱셈

문제

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

입력

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

출력

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

예제 입력 1

10 11 12

예제 출력 1

풀이

주어진 문제는 A를 B번 곱한 수를 C로 나눈 나머지를 구하면 된다.

문제만 봤을 때 쉽게 느끼겠지만 생각해야할 점이 있다.

바로 시간 제한이다. 문제에서 주어진 시간은 0.5초로 A를 B번 계속 곱하는 반복문을 돌리면 시간 복잡도에 걸리게 될 것이다.

(문제에서 A와 B가 2,147,483,647이하의 수로 제한되어져 있다)

아래와 같은 방식으로 문제를 풀게 되면 오버플로우가 발생해 런타임에러가 발생할 수 있다.

import Foundation

let input = readLine()!.split(separator: " ").map { Double(String($0))! }
let (A, B, C) = (input[0], input[1], input[2])

let result = (Int(pow(A, B)) % Int(C))
print(result)

A의 B제곱은 매우 큰 수가 될 수 있고, 그 큰 수를 C로 나누는 작업은 오버플로우를 일으킬 수 있다. 그렇기 때문에 A에 B를 바로 곱하는 것이 아닌 분할 정복을 사용하여 문제를 풀어보자.

설계

분할 정복 어떻게?

나머지를 다음과 같이 생각할 수 있다.

A * B % C = A % C * B % C
A^B % C = (A^B/2 %C) * (A^B/2 % C)

여기서 알 수 있는 점은 A의 B제곱을 한 후 C를 나눈 나머지를 구하는 것이 아니라, B제곱을 나누고 그 값을 C로 나누어 구할 수 있다는 것이다.

일단 예시로 생각해보자.

3^4 = 3^2 * 3^2과 같다.

3^5 = 3^2 * 3^2 * 3과 같다.

이렇게 되면 매번 반씩 줄어들게 계산할 수 있으므로 시간복잡도는 log(B)로 줄게된다.

구현

설계 단계에서 A에 B를 곱할 때마다 C로 나누어 구한다는 것을 알았다. 코드에 적용해보자.

1️⃣ B가 짝수

예: 3^4 = 3^2 * 3^2

(B/2) % C * (B/2) % C

2️⃣ B가 홀수

예: 3^5 = 3^2 * 3^2 * 3

(B-1/2) % C * (B-1/2) % C * A % C

전체코드

let input = readLine()!.split(separator: " ").map{Int(String($0))!}

let (A, B, C) = (input[0], input[1], input[2])

func divide(_ N: Int) -> Int {
  
  if N == 0 { return 1 }
  
  if N % 2 == 0 {
    let d = divide(N/2)
    return d % C * d % C
  } else {
    let d = divide((N - 1)/2)
    return d % C * d % C * A % C
  }
}

print(divide(B))