Today I Learned

오늘은 백준에서 코틀린 코테 공부!

구간 합 구하기 5

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

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.
여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.
표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

• 입력
  4 3
  1 2 3 4
  2 3 4 5
  3 4 5 6
  4 5 6 7
  2 2 3 4
  3 4 3 4
  1 1 4 4
• 출력
  27
  6
  64

문제 풀이

• 누적 합 배열을 사용해 각 지점까지의 합을 미리 계산해놓고 구간 합을 빠르게 계산하는 방법으로 이 문제를 풀었다.

1. 입력 글자가 길어 BufferedReader와 StringTokenizer를 이용해 입력을 받는다. 누적합을 저장할 dp 배열을 초기화한다.

2. 배열의 각 행을 입력 받아 int로 변환한 뒤 row에 저장한다. 2중 for문으로 (i, j)마다 누적합을 계산한다. 현재 위치의 누적 합은 이전 행과 이전 열의 누적 합을 이용하여 계산된다. 이 때 이전 행의 값을 이용하므로 dp[i - 1][j]과 이전 열의 값을 이용하므로 dp[i][j - 1]을 더하고, 중복으로 더해진 dp[i - 1][j - 1]은 한 번 빼준다. 마지막으로 현재 행의 값을 더해준다.

3. 출력을 한번에 하기위해 StringBuilder 변수를 하나 만든다. 쿼리의 개수 m만큼 반복하면서 각 쿼리를 처리한다. 각 쿼리는 (x1, y1)부터 (x2, y2)까지의 구간 합을 구하는 것이므로, 누적 합 배열을 이용하여 해당 구간의 합을 계산해서 결과를 StringBuilder에 추가한다.

4. StringBuilder를 출력하면 완료!

Kotlin 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()

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

    for (i in 1..n) {
        val row = br.readLine().split(" ").map { it.toInt() }
        for (j in 1..n) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + row[j - 1]
        }
    }

    val sb = StringBuilder()

    repeat(m) {
        val (x1, y1, x2, y2) = br.readLine().split(" ").map { it.toInt() }
        val result = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]
        sb.append("$result\n")
    }

    println(sb)
}