[백준] 배열 B의 값

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

16971번: 배열 B의 값

각각의 배열의 원소의 위치에 따라서 배열 B에 포함되는 횟수를 표시해보면 다음과 같습니다.

1 2 2 2 1

2 4 4 4 2

2 4 4 4 2

1 2 2 2 1

A[0][0]에 위치한 요소는 배열 B를 만드는데 한번만 사용됩니다. 반면 A[1][1]은 4번 사용됩니다. 그리고 다음과 같은 규칙을 찾을 수 있습니다. 행과 열의 처음과 마지막은 1 2....2 1과 같은 패턴을 띄고 나머지 행과 열은 2 4....4 2와 같은 패턴을 보입니다. 즉, 행과 열의 처음과 마지막과 바꾸는 경우가 아니라면 B의 값에 영향을 주지 못합니다. 따라서 각 행과 열의 누적합을 구해주고 각각 행과 열의 처음과 마지막을 바꾸어보았을 때 얻을 수 있는 최대값이 정답이 됩니다.

 

import sys

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = tuple(map(int, input().split()))
board = [
    list(map(int, input().split()))
    for _ in range(n)
]
# 행의 합
row_sum = [0 for _ in range(n)]
# 열의 합
col_sum = [0 for _ in range(m)]

def getRowSum(row):
    return board[row][0] + board[row][m - 1] + 2 * sum(board[row][1: m - 1])

def getColSum(col):
    return board[0][col] + board[n - 1][col] + 2 * sum([board[i][col] for i in range(1, n - 1)])

for i in range(n):
    if i == 0 or i == n - 1:
        row_sum[i] = getRowSum(i)
    else:
        row_sum[i] = 2 * getRowSum(i)

for i in range(m):
    if i == 0 or i == m - 1:
        col_sum[i] = getColSum(i)
    else:
        col_sum[i] = 2 * getColSum(i)

total = sum(row_sum)
ans = total

for i in range(1, n - 1):
    # 0번쨰 행과 바꾼 경우
    ans = max(ans, total + row_sum[0] - row_sum[i] // 2)
    # n - 1번쨰 행과 바꾼 경우
    ans = max(ans, total + row_sum[n - 1] - row_sum[i] // 2)
    
for i in range(1, m - 1):
    # 0번쨰 열과 바꾼 경우
    ans = max(ans, total + col_sum[0] - col_sum[i] // 2)
    # m - 1번재째 열과 바꾼 경우
    ans = max(ans, total + col_sum[m - 1] - col_sum[i] // 2)

print(ans)