[백준] 10830번: 행렬 제곱 - Kotlin[코틀린]

문제

 

10830번: 행렬 제곱

 

---

풀이

 

 곱셈 공식을 활용한 분할 정복을 수행하는 재귀 함수로 해결하면 된다. (1629번 곱셈 문제와 같다.) 재귀 함수에서는 다음과 같이 지수를 반으로 나눠가며 계산한다. 지수가 1인 경우에 입력받은 행렬을 그대로 리턴하면 된다.

 

  - 지수가 짝수인 경우
    $a^n = a^{n/2} \times a^{n/2}$

  - 지수가 홀수인 경우
    $a^n = a^{n/2} \times a^{n/2}\times a$

 

 행렬의 곱셈은 다음 이미지와 같은 방식으로 처리되며, 3중 for문으로 구현할 수 있다. 매우 큰 수의 방지를 위해 1000L으로 모듈러 연산을 해준다.

이미지 출처 - 위키 백과

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val line = br.readLine().split(' ')
    val size = line[0].toInt()
    val num = line[1].toLong()
    val matrix = Array(size) { br.readLine().split(' ').map { it.toLong() % 1000L }.toLongArray() }

    val sb = StringBuilder()
    for (row in power(matrix, num)) {
        sb.append("${row.joinToString(" ") { it.toString() }}\n")
    }

    bw.write(sb.toString())
    bw.flush()
    bw.close()
    br.close()
}

fun multi(mat1: Array<LongArray>, mat2: Array<LongArray>): Array<LongArray> {
    val size = mat1.size
    val tmp = Array(size) { LongArray(size) }

    for (i in 0 until size) {
        for (j in 0 until size) {
            for (k in 0 until size) {
                tmp[i][j] += mat1[i][k] * mat2[k][j]
                tmp[i][j] %= 1000L
            }
        }
    }

    return tmp
}

fun power(mat: Array<LongArray>, exponent: Long): Array<LongArray> {
    return when(exponent) {
        1L -> mat
        else -> {
            val n = power(mat, exponent / 2)

            if (exponent % 2 == 0L) multi(n, n)
            else multi(multi(n, n), mat)
        }
    }
}