백준 1749 점수따먹기 Kotlin (2차원 누적 합)

문제 출처 : https://www.acmicpc.net/problem/1749

1749번: 점수따먹기

문제

동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점수 따먹기라는 게임인데 그다지 재밌어 보이지는 않는다.

동주가 개발한 게임은 이렇다. 일단 N*M 행렬을 그린 다음, 각 칸에 -10,000 이상 10,000 이하의 정수를 하나씩 쓴다. 그런 다음 그 행렬의 부분행렬을 그려 그 안에 적힌 정수의 합을 구하는 게임이다.

동주가 혼자 재밌게 놀던 중 지나가는 당신을 보고 당신을 붙잡고 게임을 하자고 한다. 귀찮은 당신은 정수의 합이 최대가 되는 부분행렬을 구하여 빨리 동주에게서 벗어나고 싶다.

입력

첫째 줄에 N (1 < N < 200), M (1 < M < 200)이 주어진다. 그 다음 N개의 줄에 M개씩 행렬의 원소가 주어진다.

출력

첫째 줄에 최대의 합을 출력하라.

알고리즘 분류

• 다이나믹 프로그래밍
• 브루트포스 알고리즘
• 누적 합

풀이

순수 완전 탐색으로는 반복문이 너무 많아지게 된다.

2차원 누적 합을 이용해 반복 횟수를 줄일 수 있다.

2021.10.04 - [알고리즘 문제 풀이/백준] - 백준 2167 2차원 배열의 합 c++ (누적 합)

 

 

11	12	13
21	22	23
31	32	33

위 그래프를 2차원 누적 합 prefixSum이라 하면,

빨간 부분은 

pSum[3][3] - pSum[3][1] - pSum[1][3] + pSum[1][1]이다.

pSum[1][1]을 더해주는 이유는 -pSum[3][1] -pSum[1][3]에서 두 번 빼줬기 때문에 한 번 더해주는 것이다.

11	12	13
21	22	23
31	32	33

위에서 빨간 부분은 

pSum[3][3] - pSum[3][1]- pSum[2][3] + pSum[2][1]이다.

 

결론은, 2차원 누적합을 구하고, 이를 완전 탐색하여 전체 부분 행렬 중 최댓값을 출력하면 된다.

코드

import kotlin.math.*
val br = System.`in`.bufferedReader()

fun main() = with(System.out.bufferedWriter()){

    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    var answer =-987654321
    val arr = Array(n){
        br.readLine().split(' ').map{it.toInt()}
    }
    val pSum = Array(n+1){IntArray(m+1)}

    for(i in 1 .. n){
        for(j in 1 .. m){
            pSum[i][j] = arr[i-1][j-1]+pSum[i-1][j]+pSum[i][j-1]-pSum[i-1][j-1]
        }
    }

    for(i in 1 .. n){
        for(j in 1 .. m){
            for(ii in i .. n){
                for(jj in j .. m){
                    answer = max(answer,pSum[ii][jj]-pSum[ii][j-1]-pSum[i-1][jj] + pSum[i-1][j-1] )
                }
            }
        }
    }
    write("$answer")
    close()
}