[백준 1451 - Kotlin] 직사각형으로 나누기 (오답)

문제링크

import java.io.BufferedReader
import java.io.BufferedWriter

private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter
private lateinit var rectangle: MutableList<MutableList<Int>>
private lateinit var cumulativeSum: Array<Array<Int>>

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

    // 1. get n, m
    val (n, m) = bufferedReader
        .readLine()
        .split(" ")
        .map { it.toInt() }

    // 2. create rectangle
    rectangle = mutableListOf()
    val emptyRow = mutableListOf<Int>()
    repeat(m + 1) {
        emptyRow.add(0)
    }
    rectangle.add(emptyRow)

    // 3. get rectangle
    for (i in 1..n) {
        val row = mutableListOf(0)
        row.addAll(
            bufferedReader
                .readLine()
                .split("")
                .filter { it.isNotBlank() }
                .map { it.toInt() }
        )
        rectangle.add(row)
    }

    // 4. get cumulative sum
    cumulativeSum = Array(n + 1) { Array(m + 1) { 0 } }
    for (i in 1..n) {
        for (j in 1..m) {
            cumulativeSum[i][j] = cumulativeSum[i][j - 1] + cumulativeSum[i - 1][j] - cumulativeSum[i - 1][j - 1] + rectangle[i][j]
        }
    }

    // 5. find max answer
    var answer = 0

    // 5-1. case 1
    for (i in 1 until m - 1) {
        for (j in i + 1 until m) {
            val rect1 = getSum(1, 1, n, i)
            val rect2 = getSum(1, i + 1, n, j)
            val rect3 = getSum(1, j + 1, n, m)
            val total = rect1 * rect2 * rect3
            if (total > answer) {
                answer = total
            }
        }
    }

    // 5-2. case 2
    for (i in 1 until n - 1) {
        for (j in i + 1 until n) {
            val rect1 = getSum(1, 1, i, m)
            val rect2 = getSum(i + 1, 1, j, m)
            val rect3 = getSum(j + 1, 1, n, m)
            val total = rect1 * rect2 * rect3
            if (total > answer) {
                answer = total
            }
        }
    }

    // 5-3. case 3
    for (i in 1 until n) {
        for (j in 1 until m) {
            val rect1 = getSum(1, 1, n, j)
            val rect2 = getSum(1, j + 1, i, m)
            val rect3 = getSum(i + 1, j + 1, n, m)
            val total = rect1 * rect2 * rect3

            if (total > answer) {
                answer = total
            }
        }
    }

    // 5-4. case 4
    for (i in 1 until n) {
        for (j in 1 until m) {
            val rect1 = getSum(1, 1, i, j)
            val rect2 = getSum(i + 1, 1, n, j)
            val rect3 = getSum(1, j + 1, n, m)
            val total = rect1 * rect2 * rect3
            if (total > answer) {
                answer = total
            }
        }
    }

    // 5-5. case 5
    for (i in 1 until n) {
        for (j in 1 until m) {
            val rect1 = getSum(1, 1, i, m)
            val rect2 = getSum(i + 1, 1, n, j)
            val rect3 = getSum(i + 1, j + 1, n, m)
            val total = rect1 * rect2 * rect3
            if (total > answer) {
                answer = total
            }
        }
    }

    // 5-6. case 6
    for (i in 1 until n) {
        for (j in 1 until m) {
            val rect1 = getSum(1, 1, i, j)
            val rect2 = getSum(1, j + 1, i, m)
            val rect3 = getSum(i + 1, 1, n, m)
            val total = rect1 * rect2 * rect3
            if (total > answer) {
                answer = total
            }
        }
    }

    bufferedWriter.write("$answer\n")

    bufferedReader.close()
    bufferedWriter.close()
}

fun getSum(x1: Int, y1: Int, x2: Int, y2: Int): Int {
    return cumulativeSum[x2][y2] - cumulativeSum[x1 - 1][y2] - cumulativeSum[x2][y1 - 1] + cumulativeSum[x1 - 1][y1 - 1]
}

좋은 웹페이지 즐겨찾기