[분할정복 + 재귀] 백준 실버1 1629번: 곱셈(Swift)

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

1629번: 곱셈

Code

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

let A = ABC[0]
let B = ABC[1]
let C = ABC[2]

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

print(recursion(N: B))

풀이과정

해당 문제는 A의B승을 C로 나눈 나머지를 구하는 문제이다.

나머지 같은 경우 [XY % Z == X % Z * Y % Z] 이런식으로 식을 바꿔 풀 수 있다.

즉, [A^B % C == (A^B/2 %C) * (A^B/2 % C)]로 치환하여 풀 수 있다.

이를 재귀를 통해 반복해주면, 밑이 2인 logB의 횟수로 풀 수 있다.

때문에 A, B, C의 최대수인  2,147,483,647여도 32번이면 문제를 해결할 수 있다.

위 문제의 핵심은 A^B % C 해당식을 => (A^B/2 %C) * (A^B/2 % C)로 분할하여 생각할 수 있어야 한다.