백준 [10830] kotlin

[문제]

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

10830번: 행렬 제곱

[풀이]

그냥 단순하게 행렬을 N번 곱하면 시간초과가 난다 (B의 값이 최대 100,000,000,000이기 때문)

그렇기에 제귀를 통해 풀었다.

 

지수 법칙 - 거듭제곱의 곱 을 이용하면 간단하다

2의 5승은 2의 2승과 2의 2승그리고 2의 1승을 곱한것과 같다. 

fun mul(arr : Array<IntArray>, N : Long) : Array<IntArray>
{
    if(N == 1L) return arr
    val tmp = mul(arr,N/2)
    if(N % 2 == 1L) return matrixMul(matrixMul(tmp,tmp), arr)
    return matrixMul(tmp, tmp)
}

 

행렬의 곱은 다음과 같다.

fun matrixMul(arr1 : Array<IntArray>, arr2 : Array<IntArray>) : Array<IntArray>
{
    val tmp = Array(arr1.size){IntArray(arr1.size){0} }
    for(i in arr1.indices)
    {
        for(j in arr1.indices)
        {
            for(k in arr1.indices)
            {
                tmp[i][j] += arr1[i][k] * arr2[k][j]
                tmp[i][j] %= 1000
            }
        }
    }
    return tmp
}

이 문제에서 확인해야 할 것은 

B의 값이 최대 100,000,000,000 이므로 입출력을 받을 때 int로 받으면 안된다.

또 각 행렬의 값은 끝 세자리만 출력하므로, 매 연산마다 1000으로 나누었을 때 나머지 값을 저장해둔다.

하지만 입출력으로 

위와 같이 주어질 수 있으므로, 출력시에도 1000으로 나누었을 때 값을 출력하도록 하면, 정답이다.

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    val tmp = br.readLine().split(" ")

    var N = tmp[0].toInt()
    var B = tmp[1].toLong()
    var arr = Array(N){IntArray(N)}
    repeat(N)
    {
        i ->
        arr[i] = (br.readLine().split(" ").map { it.toInt() }.toIntArray())
    }
    val ans = mul(arr,B)
    for(i in ans)
    {
        for(j in i)
        {
            val t = j % 1000
            bw.write("$t ")
        }
        bw.write("\n")
    }

    bw.flush()
    bw.close()
}

fun mul(arr : Array<IntArray>, N : Long) : Array<IntArray>
{
    if(N == 1L) return arr
    val tmp = mul(arr,N/2)
    if(N % 2 == 1L) return matrixMul(matrixMul(tmp,tmp), arr)
    return matrixMul(tmp, tmp)
}

fun matrixMul(arr1 : Array<IntArray>, arr2 : Array<IntArray>) : Array<IntArray>
{
    val tmp = Array(arr1.size){IntArray(arr1.size){0} }
    for(i in arr1.indices)
    {
        for(j in arr1.indices)
        {
            for(k in arr1.indices)
            {
                tmp[i][j] += arr1[i][k] * arr2[k][j]
                tmp[i][j] %= 1000
            }
        }
    }
    return tmp
}