https://www.acmicpc.net/problem/11660
이차원 배열에서 구간의 합을 구하는 문제이다.
예제인 (2, 2)부터 (3, 4)까지의 합이 27이라는 점에서 주의해야할 점이
(2, 2) ~ (3, 4) 사이의 직사각형 범위 내의 합을 구하는 문제임을 주의해야 한다.
합을 구하는 케이스의 개수인 M이 최대 100,000이므로 매 케이스마다 직접 합을 구한다면 워스트 케이스의 경우 1024 x 1024의 이차원 배열을 10만번 순회하게 되어 시간 초과가 날 수 있다.
따라서 직접 탐색 대신 구간 합을 다이나믹 프로그래밍의 개념을 적용하여 풀이하는 방법을 생각하였다.
먼저 주어진 이차원 배열과 같은 크기의 이차원 배열을 준비한다.
그리고 배열의 [i][j] = (1, 1)부터 [i][j]까지의 구간합이 되도록 배열을 채운다.
이 배열을 채우는 방법은 다음과 같다.
- 맨 왼쪽 위를 [0][0]라 하면, [0][0]위치를 채운다.
- [0][1] 부터 [0][3]까지 반복문을 통해 이전 합 + 현재 값 으로 채운다.
- 유사하게 [1][0]부터 [3][0]까지 이전 합 + 현재 값으로 채운다.
- [1][1]부터 [3][3]까지 이중 반복문을 통해 빈 칸을 채운다.
4번에 대한 자세한 설명이다.
[1][1]에 해당하는 값인 8은 원래 표의 1+2+2+3을 더한 값이다.
이는 8의 위쪽 값(3) + 왼쪽 값(3) + 현재 위치 값(3) - 겹치는 왼쪽 위 값(1) 과 같다.
왼쪽 위부터 X까지의 합을 구한다고 하면, 노란 범위의 합인 b의 값과 파란 범위의 값인 c의 값을 더한 뒤 겹치는 초록 범위의 값인 a를 빼 주고, 빨간 범위의 현재 값을 더하면 16칸의 합이 된다.
이 원리를 이용해 위의 [1][1]부터의 합으로 나타낸 이차원 배열을 만든다.
그럼 만든 이차원 배열을 통해 정답을 도출해 낼 수 있다.
[2][2]부터 [3][3]까지의 합을 구한다고 해 보자.
27은 [1][1]부터 [3][3]까지의 합이고, 64는 [1][1]부터 [4][4]까지의 합이다.
위 합 정보로 구하려는 파란 범위의 합의 값을 구할 수 있다.
잘 보일지 모르겠지만 전체 64까지의 사각형에서 노란 사각형과 하늘색 사각형을 빼고 두번 뺐던 주황색 사각형을 더하면 된다.
합 배열을 sum이라고 하면 다음이 성립한다.
sum[4][4] - sum[2][4] - sum[4][2] + sum[2][2]
(64) - (24) - (24) + (8) = 24
[x1][y1] 부터 [x2][y2] 라고 일반화하면 다음과 같다.
sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val (N, M) = readLine().split(' ').map { it.toInt() }
val field = Array(N) { readLine().split(' ').map { it.toInt() }.toTypedArray() }
val sums = Array(N) { IntArray(N){0} }
sums[0][0] = field[0][0]
for(i in 1 until N)
sums[0][i] = sums[0][i - 1] + field[0][i]
for(i in 1 until N)
sums[i][0] = sums[i - 1][0] + field[i][0]
for(i in 1 until N){
for(j in 1 until N){
sums[i][j] = sums[i-1][j] + sums[i][j-1] + field[i][j] - sums[i-1][j-1]
}
}
fun getSum(x1: Int, y1: Int, x2: Int, y2: Int): Int{
return when{
x1 == x2 && y1 == y2 -> field[x1][y1]
x1 == 0 && y1 == 0 -> sums[x2][y2]
x1 == 0 && y1 > 0 -> sums[x2][y2] - sums[x2][y1 - 1]
x1 > 0 && y1 == 0 -> sums[x2][y2] - sums[x1 - 1][y2]
else -> sums[x2][y2] - sums[x1 - 1][y2] - sums[x2][y1 - 1] + sums[x1 - 1][y1 - 1]
}
}
val answer = StringBuilder()
val cases = Array(M){readLine().split(' ').map{it.toInt()}}
cases.forEach {
answer.append("${getSum(it[0] - 1, it[1] - 1, it[2] - 1, it[3] - 1)}\n")
}
print(answer.toString())
}위 내용을 적용한 코드이다.
sums에 [1][1]부터의 합을 설명한 대로 구해 넣었다.
이 배열을 이용해 구간합을 구하는 getSum함수를 작성했고, 그림으로 설명한 대로 [x2][y2]사각형에서 직사각형 두 개를 빼고 두번 뺀 사각형을 더해 주었다.
x1 또는 y1이 0인 경우, -1을 하면 음수가 되므로 이에 대한 처리를 따로 해 주었다(when에서)
