거듭 제곱 구하기 L

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 거듭제곱의 경우 재귀함수, 단순 완전탐색으로 문제를 해결할 수 있지만, 위 문제의 크기를 보면 m이 10^18 이므로, O(m)의 시간복잡도로도 문제를 해결할 수 없음
• 따라서 시간복잡도를 개선해야 하는데, 지수의 경우 거듭 제곱끼리 곱하게 되면 지수끼리는 덧셈을 하게되는 성질을 이용하게 되면 시간 복잡도를 줄일 수 있음
• m(지수)가 짝수일 경우는 n^(m / 2)를 두번 곱함으로써 n^m을 구할 수 있고, 홀수의 경우 n^(m - 1) * n을 통해서 n^m을 구할 수 있음
• 따라서 m == 0이 될 때 까지(기저조건) 이를 반복하게 되면, O(log m)의 시간복잡도로 문제를 해결할 수 있음

5. 전체 코드

//MARK: - 거듭 제곱 구하기 L

//MARK: - Framework
import Foundation

//MARK: Function
func getPowerL(_ n: Int, _ m: Int64) -> Int64 {
    if m == 0 {
        return 1
    }
    
    if m % 2 == 0 {
        let result: Int64 = getPowerL(n, m / 2) % 10007
        return result * result % 10007
    } else {
        return Int64(n) * getPowerL(n, m - 1) % 10007
    }
}

func solution() -> Void {
    //MARK: - Input
    guard let input: [String] = readLine()?.components(separatedBy: " ") else { return }
    
    let n: Int = input.map { Int($0) }[0] ?? 0
    let m: Int64 = input.map { Int64($0) }[1] ?? 0
    var result: Int64 = 0
    
    //MARK: - Process
    result = getPowerL(n, m)
    
    //MARK: - Output
    print(result)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.