BOJ-1629 곱셈 Swift

문제

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

입력

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

출력

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

내가 푼 풀이

접근방법: 수학, 분할정복

이 문제는 지수법칙과 모듈러연산의 분배법칙을 알고있다면 풀 수있다.

본인은 몰라서 검색을 통해 알게되었다..

 

지수법칙:  $x^{ab} = x^{a} \times x^{b}$

모듈러연산의 분배법칙:$(A\times B)\mathrm{mod}C = (A \mathrm{mod}C\times B\mathrm{mod}C)\mathrm{mod}C$

 

분할: 지수법칙 이용

$m = B / 2$

B가 짝수: $A^{C} = A^{m} \times A^{m} $

B가 홀수:$A^{C} = A^{m} \times A^{m+1} $

 

정복: 분배법칙 이용

$ B \doteq 1 $  $\mathrm{return} $  $A\div C $

$B\neq 1$ $((A^{m} \div C) \times (A^{m}\div C)) \div C $ , $((A^{m} \div C) \times (A^{m+1}\div C)) \div C $

B가 1이 아니라면 두가지 경우의 수가 있다.(홀수, 짝수)

 

이렇게 m이 1이될때까지 분할후 m이 1이되면 정복과정을 진행하여 결과를 도출한다.

 

직관적으로 코드를 짰다가 함수 재귀호출을 너무많이하여 시간초과가 났다.

<시간초과>

// 시간초과
func mul2(_ n: Int,_ c: Int,_ d: Int) -> Int {
    if c == 1 { return n%d}
    let m = c/2
    if c % 2 == 0{
        return (mul(n, m, d)%d * mul(n, m, d)%d)%d
    } else {
        return (mul(n, m, d)%d * mul(n, m+1, d)%d)%d
    }
    
}

 

<수정한 코드>

import Foundation

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

// 분할 정복
func mul(_ n: Int,_ c: Int,_ d: Int) -> Int {
    
    // c가 1이될때까지 분할하고, 1이됬다면 정복과정을 진행한다.
    if c == 1 { return n%d}
    
    // 지수법칙을 이용하여 c/2번 곱한 나머지를 구한다.
    let m = mul(n, c/2, d)
    
    // c가 짝수라면 곱해주고,
    // c가 홀수라면 c = 5 -> n^2 * n^2 * n^1
    // n을 한번곱한 나머지를 추가로 곱해준다.(분배법칙)
    if c % 2 == 0{
        return m*m%d
    } else {
        return m*m%d*n%d
    }
    
}
print(mul(A, B, C))