Today I Learned

오늘도 코테 연습!

곱셈

백준 1629번 https://www.acmicpc.net/problem/1629

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

• 입력
  10 11 12
• 출력
  4

문제 풀이

• A를 B번 곱한 뒤 C로 나눈 나머지를 구하는 문제다. 효율성이 중요한 문제라고 생각되어 분할 정복 알고리즘을 이용해 문제를 해결했다.

1. 일반적으로 A^B를 구하기 위해 A를 B번 구하는 것은 B가 큰 경우에는 비효율적이다.

2. 대신 분할정복 알고리즘을 이용해 지수 B를 반으로 나누고 재귀적으로 A^(B/2)를 계산한다.

3. B가 홀수인 경우와 짝수인 경우를 구분해 홀수인 경우에는 A^(B/2)를 한번 더 곱해준다.

4. 마지막으로 C로 나눈 나머지를 구하면 완료!

Kotlin 코드

fun main() {
    val (A, B, C) = readln().split(" ").map { it.toLong() }
    println(power(A, B, C))
}

fun power(A: Long, B: Long, C: Long): Long {
    if (B == 0L) return 1L

    var temp = power(A, B / 2, C) % C
    temp = (temp * temp) % C

    if (B % 2 == 0L) {
        return temp
    } else {
        return (temp * A) % C
    }
}