[Koltin] 백준 1749번 - 점수따먹기

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

1749번: 점수따먹기

유형

누적 합, 완전 탐색

풀이

부분 행렬의 최대 값을 구하는 문제이다. 부분 행렬 or 배열에서 연속된 부분 합을 빠르게 구하는 방법으로는 누적 합이 있다. 일단 그것을 배제하고 단순하게 완전 탐색으로 모든 부분 행렬의 합을 구하려고 한다면, 아래와 같이 6중 for문을 사용하게 된다.

// 부분 행렬의 왼쪽 위 끝 점
for (startRow in 0 until rowSize) {
    for (startCol in 0 until colSize) {
        // 오른쪽 아래 끝 점
        for (endRow in startRow until rowSize) {
            for (endCol in startCol until colSize) {
                var partSum = 0
                // 부분 행렬 안에서 포인터 이동
                for (row in startRow..endRow) {
                    for (col in startCol..endCol) {
                        partSum += matrix[row][col]
                    }
                }
            }
        }
    }
}

시간 복잡도까지 안가도 이건 안되겠다는 게 느껴지지만ㅋㅋ, 대충 따져봐도 O(N^6)에 가깝기 때문에 이 방법으론 안된다.

 

위에서 얘기한대로 누적 합 방법을 사용하면 완전 탐색으로도 시간 안에 풀 수 있다. 누적 합이 위의 코드에서 맨 안쪽에 있는 실제 부분 합을 구하는 이중 for문을 수식 하나로 바꿔주기 때문이다. 즉, 부분 행렬의 시작 점과 끝 점만 알면 누적 합을 구하는 수식을 통해 O(1)로 합을 구할 수 있다.

ex) 부분 행렬 (2,3) ~ (5,7)의 합

= prefixSum[5][7] - prefixSum[2-1][7] - prefixSum[5][3-1] + prefixSum[2-1][3-1]

for (startRow in 0 until rowSize) {
    for (startCol in 0 until colSize) {
        for (endRow in startRow until rowSize) {
            for (endCol in startCol until colSize) {
                var currentPrefixSum = prefixSum[endRow][endCol]
                // 시작 점이 0행이면 뺄 구간이 없다.
                if (startRow > 0) currentPrefixSum -= prefixSum[startRow-1][endCol] 
                if (startCol > 0) currentPrefixSum -= prefixSum[endRow][startCol-1] // 열도 마찬가지
                if (startRow > 0 && startCol > 0)  currentPrefixSum += prefixSum[startRow-1][startCol-1]
                maxPartSum = currentPrefixSum.coerceAtLeast(maxPartSum)
            }
        }
    }
}

 

따라서 시간 복잡도는 시작점이 (0,0)일 때 끝 점이 (0,0)에서 (n-1, n-1)인 경우, 시작 점이 (0,1)일 때 끝 점이 (0,1)에서 (n-1, n-1)인 경우의 수와 같이 모든 부분 행렬의 경우의 수를 따져보면 알 수 있다.

 

시작 점이 (0,0)일 경우 n^2, (0,1)이면 n*(n-1), ... , (0, n-1)이면 n,

1행에서는 (1,0)이면 (n-1)*n, (1,1)이면 (n-1)*(n-1), ..., (1, n-1)이면 n-1이 된다.

이런 식으로 전부 구한다면 연산 횟수 = n*(1+...+n) + (n-1)*(1+...+n) + ... + (1+...+n) = (1+...+n)*(1+...+n)이며, n에 199를 넣어보면 대략 4억이다.

풀이 순서

1. (0,0)에서 각 점까지의 누적 합을 구한다.

2. 가능한 모든 시작 점과 끝 점을 확인하면서 모든 부분 행렬의 합을 구한다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (rowSize, colSize) = readLine().split(" ").map(String::toInt)
    val matrix = Array(rowSize) {
        val st = StringTokenizer(readLine())
        IntArray(colSize) { st.nextToken().toInt() }
    }
    val prefixSum: Array<IntArray> = calculatePrefixSum(matrix) // 0행0열에서부터의 누적합 기록
    var maxPartSum = matrix[0][0]
    
    // 부분행렬 [startRow][startCol] ~ [endRow][endCol]의 합
    for (startRow in 0 until rowSize) {
        for (startCol in 0 until colSize) {
            for (endRow in startRow until rowSize) {
                for (endCol in startCol until colSize) {
                    var currentPrefixSum = prefixSum[endRow][endCol]
                    if (startRow > 0) currentPrefixSum -= prefixSum[startRow-1][endCol]
                    if (startCol > 0) currentPrefixSum -= prefixSum[endRow][startCol-1]
                    if (startRow > 0 && startCol > 0)  currentPrefixSum += prefixSum[startRow-1][startCol-1]
                    maxPartSum = currentPrefixSum.coerceAtLeast(maxPartSum)
                }
            }
        }
    }

    print(maxPartSum)
}

// 누적합 배열 반환
fun calculatePrefixSum(matrix: Array<IntArray>): Array<IntArray> {
    val prefixSum = Array(matrix.size) { IntArray(matrix[0].size) }
    
    prefixSum[0][0] = matrix[0][0]
    // 0행 누적합
    for (i in 1 until prefixSum[0].size) {
        prefixSum[0][i] = prefixSum[0][i-1] + matrix[0][i]
    }
    // 0열 누적합
    for (i in 1 until prefixSum.size) {
        prefixSum[i][0] = prefixSum[i-1][0] + matrix[i][0]
    }

    // 1행1열에서 row행col열까지의 누적합
    for (row in 1 until prefixSum.size) {
        for (col in 1 until prefixSum[0].size) {
            prefixSum[row][col] =
                prefixSum[row][col-1] + prefixSum[row-1][col] + matrix[row][col] - prefixSum[row-1][col-1]
        }
    }
    
    return prefixSum
}