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

문제

---

생각하기

---

• 누적 합 문제이다.
  • 2차원 배열 누적 합을 사용해서 최적화를 진행한다.

동작

결과

코드

---

Kotlin

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var M = 0

private lateinit var board: Array<IntArray>

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

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    // 누적 합 계산하기
    repeat(M) {
        StringTokenizer(br.readLine()).run {
            val x1 = nextToken().toInt()
            val y1 = nextToken().toInt()
            val x2 = nextToken().toInt()
            val y2 = nextToken().toInt()

            sb.append(prefixSum(x1, y1, x2, y2)).append('\n')
        }
    }


    return sb.toString()
} // End of solve()

private fun prefixSum(x1: Int, y1: Int, x2: Int, y2: Int): Int {
    return board[x2][y2] - board[x1 - 1][y2] - board[x2][y1 - 1] + board[x1 - 1][y1 - 1]
} // End of prefixSum()

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt()
        M = nextToken().toInt()
    }

    board = Array(N + 1) { IntArray(N + 1) }

    for (i in 0 until N) {
        StringTokenizer(br.readLine()).run {
            for (j in 0 until N) {
                val tmp = nextToken().toInt()
                board[i + 1][j + 1] = board[i][j + 1] + board[i + 1][j] - board[i][j] + tmp
            }
        }
    }
} // End of input()