백준 1915 코틀린

일반적인 dp 문제와 다르게 점화식을 세워 푸는 풀이보다는 메모 라이징 특성을 이용하여 푸는 문제이다.

현재 좌표에 값이 1일 때 좌표의 왼쪽, 왼쪽 위, 위에 값이의 최솟값이 1이라면 2x2의 정사각형을 만들 수 있고 1의 값을 2로 대체해 주면(메모 라이징) 해당 좌표의 왼쪽, 왼쪽 위, 위에 값이 1이라는 사실을 알 수 있다.

이런 식으로 왼쪽, 왼쪽 위, 위에 값이의 최솟값이 2이라면 3x3의 정사각형을 만들 수 있다.

ex)
0111
0122
0123

ex)
0011
0112
0122

따라서, 현재 좌표의 값이 1일 때 왼쪽, 왼쪽 위, 위에 값의 최솟값에 1을 더한 값이 현재 좌표에서 만들 수 있는 최대 크기의 정사각형이므로 좌표들의 값들 중 최댓값을 출력하면 정답이 된다.

 

import kotlin.math.min

fun main() {
    val input = readLine()!!.toString().split(" ")

    val n = input[0].toInt()
    val m = input[1].toInt()

    val dp = Array(n + 1) { IntArray(m + 1) }

    var max = 0

    for (i in 1 until n + 1) {
        val line = readLine()!!
        for (j in 1 until m + 1) {
            val value = line[j - 1].toString().toInt()

            if (value > 0 && max == 0) {
                max = 1
            }

            dp[i][j] = value
        }
    }

    for (i in 1 until n + 1) {
        for (j in 1 until m + 1) {
            val min = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]))

            if (min != 0 && dp[i][j] == 1) {
                dp[i][j] = min + 1

                if (max < min + 1) {
                    max = min + 1
                }
            }
        }
    }

    println(max * max)
}