[Python/파이썬] 백준 16971번 배열 B의 값

 

16971번: 배열 B의 값

 

문제

크기가 N×M인 배열 A가 있을 때, 다음과 같은 방법을 이용해서 크기가 (N-1)×(M-1)인 배열 B를 만들 수 있다.

• B[i][j] = A[i][j] + A[i+1][j] + A[i+1][j+1] + A[i][j+1] (1 ≤ i < N, 1 ≤ j < M)

배열의 값은 배열의 모든 원소를 합한 값이다.

배열 A에서 임의의 두 행이나 임의의 두 열의 위치를 교환할 수 있다. 배열 A에서 교환을 최대 1번 수행해서 만들 수 있는 배열 B의 값의 최댓값을 구해보자.

입력

첫째 줄에 배열 A의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 배열의 원소가 주어진다. 배열은 정수로만 이루어져 있다.

출력

만들 수 있는 배열 B의 값 중 최댓값을 출력한다.

출력

• 2 ≤ N, M ≤ 1,000
• -1,000 ≤ $A_{i,j}$ ≤ 1,000

 

코드

n, m = map(int, input().split())
map_data = []
for _ in range(n):

    map_data.append(list(map(int, input().split())))

# 가장 작은 행 찾기
min_row_sum = int(1e9)
first_row, last_row = 0, 0
total_r = 0
for i in range(n):
    row_sum = map_data[i][0] + map_data[i][m-1]
    for j in range(1, m-1):
        row_sum += 2 * map_data[i][j]
    total_r += (row_sum * 2)
    if i == 0:
        first_row = row_sum
    elif i == n-1:
        last_row = row_sum
    else:
        if min_row_sum > row_sum:
            min_row_sum = row_sum
# 안 바꾸는게 최대
if min_row_sum > max(first_row, last_row):
    total_r -= (first_row + last_row)
# 테두리 2행 중 큰 거와 바꾸기
else:
    total_r -= (min_row_sum + min(first_row, last_row))

# 가장 작은 열 찾기
min_col_sum = int(1e9)
first_col, last_col = 0, 0
total_c = 0
for j in range(m):
    col_sum = (map_data[0][j]+map_data[n-1][j])
    for i in range(1, n-1):
        col_sum += 2 * map_data[i][j]
    total_c += (col_sum * 2)
    if j == 0:
        first_col = col_sum
    elif j == m-1:
        last_col = col_sum
    else:
        if min_col_sum > col_sum:
            min_col_sum = col_sum
# 안 바꾸는게 최대
if min_col_sum > max(first_col, last_col):
    total_c -= (first_col + last_col)
# 테두리 2열 중 큰 거와 바꾸기
else:
    total_c -= (min_col_sum + min(first_col, last_col))
print(max(total_r, total_c))