[BOJ/백준][Silver1] 11660 : 구간 합 구하기5 (Kotlin)

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

11660번: 구간 합 구하기 5

 

[난이도] Silver1
[유형] DP

[풀이]
입력을 받으면서 sum[i][j]에 (1,1)~(i,j)까지의 합을 저장합니다.
현재 입력은 (i,j)의 값이 r[j-1]일때, sum[i][j]는 아래와 같이 구할 수 있습니다.
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+r[j-1]
sum[i-1][j-1]이 두번 두해졌기 때문에 한번 빼는 것입니다.

쿼리 (x1,y1)~(x2,y2) 은 아래와 같이 구할 수 있습니다.
sum[y2][x2]-sum[y1-1][x2]-sum[y2][x1-1]+sum[y1-1][x1-1]
이번엔 반대로 sum[y1-1][x1-1]이 두번 빠졌으므로 한번 더해주는 것입니다.

println을 사용하면 시간초과가 나서 bufferedWriter를 이용해야 했습니다.

 

import java.util.*
val bw = System.`out`.bufferedWriter()
var sum = Array(1025){IntArray(1025)}
fun main() = with(System.`in`.bufferedReader()){
    val (N,M) = readLine().split(' ').map{it.toInt()}
    for(i in 1..N){
        val r = readLine().split(' ').map{it.toInt()}
        for(j in 1..N)  sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+r[j-1]
    }
    repeat(M){
        val (y1,x1,y2,x2) = readLine().split(' ').map{it.toInt()}
        val ret = sum[y2][x2]-sum[y1-1][x2]-sum[y2][x1-1]+sum[y1-1][x1-1]
        bw.write(ret.toString()+'\n')
    }
    bw.flush()
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/11660.cpp