문제 풀이
브루트포스, 누적합
arr[i][j] = 좌표 (1, 1)에 있는 나무부터 (i, j)에 있는 나무까지의 누적합
answer = K x K 크기의 정사각형 모양으로 수확했을 때 얻을 수 있는 최대 수익
k = 수확하는 정사각형 모양의 크기
1부터 N까지의 i, j에 대해 입력을 받으면서 윗칸과 옆칸까지의 누적합 arr[i - 1][j], arr[i][j - 1]을 더해주고 이 과정에서 중복으로 더해지는 arr[i - 1][j - 1]을 빼줘서 누적합을 저장함
저장한 이후에 그 칸을 정사각형의 가장 오른쪽 아랫칸으로 하는 1 x 1 크기의 정사각형 모양부터 최대로 가능한 K x K 크기의 정사각형 모양으로 가능한 수익을 확인하고 최댓값을 answer에 저장함
모든 칸에 대해 반복하면 구하는 최대 수익이 answer에 저장되므로 출력하면 정답
풀이 설명
N × N 크기의 정사각형 모양 과수원이 있고, N × N 개의 사과나무가 1 × 1 크기의 간격으로 모든 칸에 심어져있다.
농부 형곤이가 가을을 맞아 사과를 수확하려는데, 땅주인 신영이가 "너는 과수원 내에 사과나무를 K × K 의 크기의 정사각형 모양으로만 수확해 가져갈 수 있어, 이때 K는 1보다 크거나 같고 N보다 작거나 같은 정수라구! 나머지는 내가 먹을께! 하하!" 라고 통보했다.
하나의 사과나무를 수확할 때, 사과를 통해 얻을 수 있는 이익과 노동비로 빠져나가는 손해가 동시에 이루어진다.
그래서 형곤이는 나무의 위치를 좌표로 하여, 사과를 통해 얻은 이익과 노동비를 더한 총이익을 2차원 배열의 형태로 정리했다.
악독한 땅주인 신영이로부터 고통받는 귀여운 형곤이에게 최대 총이익을 안겨주고 싶은 당신, 형곤이를 도와주자!
K x K 크기의 정사각형 모양으로 수확하는 것을 반복문을 이용해 매번 의 시간 복잡도로 구하는 것은 비효율적이므로 누적합을 구해놓고 계산하는 것이 더 빠르다.
그러므로 가장 왼쪽 윗 칸인 (1, 1)에 있는 나무부터 (i, j)에 있는 나무까지의 수익을 누적합으로 구해 저장하는 배열 arr을 정의한다. 이때 K x K 크기의 수익을 구할 때 K 칸 위쪽, 왼쪽의 누적합을 빼고 K칸 왼쪽 위 칸의 누적합을 다시 더해주어야 하므로 배열을 N + 1크기로 정의하고 인덱스를 1을 기준으로 해야 한다.
그렇게 정의한 배열을 채워야 하므로 반복문을 이용해 해당 칸의 수익을 입력받고 그 칸의 왼쪽 칸까지의 누적합과 위쪽 칸까지의 누적합을 더해주어야 누적합이 계산이 되는데 여기서 왼쪽 위칸까지의 누적합이 중복으로 더해지므로 이를 빼주어야 한다.
누적합을 구하고 다시 모든 칸들을 확인하며 K x K 크기의 수익을 확인해도 되지만 입력을 받으면서 해당 칸을 정사각형의 가장 오른쪽 아래 칸으로 하는 정사각형의 수익의 합을 계산한다면 반복문을 다시 사용할 필요가 없어진다.
그러므로 누적합을 계산한 이후 문제에서 K가 1부터 N까지일 수 있다고 했으므로 현재 좌표가 (i, j)라고 하면 정사각형이 되려면 K가 i 또는 j중 작은 값까지만 될 수 있으므로 K를 1부터 그 작은 값까지 1씩 증가시키며 그때의 정사각형의 수익을 계산하고 이때의 최댓값을 answer에 저장한다.
이렇게 모든 칸에 대해 누적합을 계산하며 K x K 크기의 정사각형의 수입의 최댓값을 answer에 저장하면 구하는 값이 answer에 저장되는 것이므로 출력하면 정답이 된다.
소스 코드
import java.io.StreamTokenizer
fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
fun nextInt(): Int{
nextToken()
return nval.toInt()
}
val N = nextInt()
var answer = Int.MIN_VALUE
val arr = Array(N + 1){ IntArray(N + 1) }
for(i in 1..N){
for(j in 1..N){
arr[i][j] = nextInt() + arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1]
var k = 1
while(i - k >= 0 && j - k >= 0){
answer = maxOf(answer, arr[i][j] - arr[i - k][j] - arr[i][j - k] + arr[i - k][j - k])
k++
}
}
}
println(answer)
}