25589 푸앙이와 코인 (백준, python3)

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

시간 제한	메모리 제한
1초	1024MB

문제

N*N 크기의 격자 위에 칸마다 코인이 놓여있다.

푸앙이는 격자 위에 한 변의 길이가 1 이상 N이하인 정사각형 그물을 만들어 그 안의 코인을 얻을 수 있다. 하지만 그물이 포함하는 칸 개수의 제곱에 해당하는 코인을 지불해야 한다.

그물은 반드시 N*N크기의 격자 안에 완전히 포함 되어야 하고, 한 번 그물을 친 칸에는 다시 그물을 칠 수 없다.

푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 구하시오.

 

입력

첫 번째 줄에 정수 N(2 ≤ N ≤ 400)이 주어진다.

두 번째 줄부터 N개의 줄에는 칸에 놓여 있는 코인의 수가 1행부터 차례대로 주어진다. 칸에 놓여 있는 코인의 수는 10^9 이하의 양의 정수이다.

 

출력

첫 번째 줄에 푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 출력한다.

 

---

풀이

N의 범위가 400으로 매우 만만해 보입니다. 최대 크기의 격자인 400*400에 그물을 한 번 치는 경우의 수를 생각해 봅시다. 400*400으로 1가지, 399*399로 2*2가지, 398*398로 3*3가지,... 1*1로 400*400가지, 모두 더해보면 21,413,400가지입니다. 시도해 볼 만한 숫자이지만 그물을 두 번 쳐야 한다는 점이 문제입니다. 2천만 가지의 경우로 그물을 한 번 쳤을 때, 나머지 그물을 치는 경우를 모두 구해보면 경우의 수가 너무 커집니다.

 

문제에서 주어진 세 가지 조건을 봅시다. "한 변의 길이가 1이상 N이하인 정사각형 그물", "그물은 반드시 N*N크기의 격자 안에 완전히 포함", "한 번 그물을 친 칸에는 다시 그물을 칠 수 없다." 이 세 조건에 맞게 그물을 친다면 그물의 배치는 이런 특징을 갖게 됩니다.

두 개의 그물은 반드시 전체 격자를 상하, 또는 좌우로 분할한 두 개의 직사각형 안에 따로 포함됩니다. 이걸 두고 보면 전체 격자를 이렇게 분할해 볼 수 있습니다.

격자를 a, c와 b, d로 상하 분할하는 지점을 i로, a, b와 c, d로 좌우 분할하는 지점을 j라고 합시다. 이제 이 안에 두 개의 그물을 배치한다면 다음 두 가지 경우만 가능합니다.

1. a, c에 하나의 그물을 배치하고 b, d에 나머지 하나를 배치
2. a, b에 하나의 그물을 배치하고 c, d에 나머지 하나를 배치

각각의 그물이 어디에 어떻게 있어야 하는가를 따로 구한다면 앞서 말했듯이 시간초과입니다. 하지만 a, b 직사각형에서 만들어지는 가장 좋은 그물의 정보가 이미 있다면 400개의 i와 400개의 j에 대해 O(400*400)의 시간 안에 가장 좋은 두 개의 그물을 찾아낼 수 있습니다. 그 전에 전체 격자를 상하 또는 좌우로 나누어 분할했을 때 분할 된 직사각형 안에서 만들 수 있는 가장 좋은 그물로 얻는 코인의 양을 다음 배열로 관리합니다.

left[i] = i번째 칸을 기준으로 왼쪽 직사각형에서 얻는 최적해
right[i] = i번째 칸을 기준으로 오른쪽 직사각형에서 얻는 최적해
up[j] = j번째 칸을 기준으로 위쪽 직사각형에서 얻는 최적해
down[j] = j번째 칸을 기준으로 아래쪽 직사각형에서 얻는 최적해

그럼 i를 기준으로 좌우 분할한다면 left[i]와 right[i + 1]로 가장 좋은 두 개의 그물을 찾을 수 있습니다. 상하 분할한다면 up[i], down[i + 1]입니다.

 

왼쪽 윗 칸이 a + 1, b + 1로 시작되고 한 변의 길이가 k인 정사각형의 그물을 생각해 봅시다.

주황색 영역에 친 그물로 얻는 코인을 coin(a, b, k)라고 하겠습니다. 왼쪽 위 끝 칸이 a, b가 아닌 이유는 이게 점이 아니라 칸이기 때문입니다. a+1로 시작해야 a+k가 k번째 칸이 됩니다. 그럼 이 그물로 인해 전체 격자는 4가지 방법으로 분할되고, 그물이 포함되는 배열은 이렇습니다.

1) 그물의 왼쪽변으로 좌우 분할, 그물은 right[b + 1]에 포함
2) 그물의 오른쪽변으로 좌우 분할, 그물은 left[b + k]에 포함
3) 그물의 윗변으로 상하 분할, 그물은 down[a + 1]에 포함
4) 그물의 아랫변으로 상하 분할, 그물은, up[a + k]에 포함

그럼 이제 대강 2천만 가지의 그물을 모두 만들어보며 left, right, up, down 배열의 최적해를 각각 정리하고 400*400가지의 분할 지점에 따라 좌우, 상하 직사각형의 두 그물을 확인해보면 O(N^3)으로 가장 좋은 두 개의 그물을 찾을 수 있습니다.

 

정답 코드

import sys
input = sys.stdin.readline
def solution():
    n = int(input())
    coins = [list(map(int, input().split())) for _ in range(n)]
    quad = [i ** 4 for i in range(400)]
    
    # 그물로 얻는 코인을 확인
    def net(a, b, k):
        ret = -quad[k]
        ret += coins[a + k][b + k]
        if a >= 0 : ret -= coins[a][b + k]
        if b >= 0: ret -= coins[a + k][b]
        if a >= 0 and b >= 0 : ret += coins[a][b]
        return ret
        
    # 좌, 우, 상, 하의 최적 그물을 관리할 배열
    l = [0] * n
    r = [0] * n
    u = [0] * n
    d = [0] * n
    
    # 격자의 누적합 생성
    for i in range(n):
        for j in range(1, n):
            coins[i][j] += coins[i][j - 1]
    for j in range(n):
        for i in range(1, n):
            coins[i][j] += coins[i - 1][j]
    
    # 가능한 모든 그물로 분할 영역의 최적해 구하기
    for k in range(1, 400):
        for i in range(-1, n - k):
            for j in range(-1, n - k):
                sq = net(i, j, k)
                u[i + k] = max(u[i + k], sq)
                d[i + 1] = max(d[i + 1], sq)
                l[j + k] = max(l[j + k], sq)
                r[j + 1] = max(r[j + 1], sq)
    for i in range(1, n):
        if l[i] < l[i - 1]: l[i] = l[i - 1]
        if u[i] < u[i - 1]: u[i] = u[i - 1]
    for i in range(n - 2, -1, -1):
        if r[i] < r[i + 1]: r[i] = r[i + 1]
        if d[i] < d[i + 1]: d[i] = d[i + 1]
        
    # 모든 칸을 기준으로 상하 또는 좌우 분리된
    # 두 직사각형에서 최적해 탐색
    res = 0
    for i in range(1, n):
        if l[i - 1] + r[i] > res:
            res = l[i - 1] + r[i]
        if u[i - 1] + d[i] > res:
            res = u[i - 1] + d[i]
    print(res)
solution()