[백준/16971] 배열 B의 값 (Python)

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

16971번: 배열 B의 값

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:24:20

 

---

 

문제 설명

 

 

크기가 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의 값 중 최댓값을 출력한다.

 

입력 예시

 

3 3
9 8 7
3 2 1
6 5 4

 

출력 예시

 

92

 

 

---

 

풀이

 

 

배열 B의 값에 영향을 미치는 A의 값들을 생각해보자.

 

1	2	2	2	1
2	4	4	4	2
2	4	4	4	2
2	4	4	4	2
1	2	2	2	1

 

꼭지점에는 단 하나의 값만 영향을 미치고, 꼭지점을 제외한 모서리는 두 개의 값에 영향을 미친다. 나머지는 4개의 값에 영향을 미친다.

또한, 행과 열의 측면에서 비교해 보면 1, N번째는 1배, 나머지 경우는 2배라고 볼 수 있다.

즉 행과 열에 대해, (모서리가 아닌 값 중 최솟값)과 (모서리값중 최댓값)을 교환하는 각 두 가지 경우, 그리고 원래 경우 총 5가지를 비교하면 된다. 이 때, 교환하는 경우는 (원래 합) - (모서리가 아닌 값 중 최솟값) + (모서리값 중 최댓값)이 될 것이다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
nums = [list(map(int, input().split())) for _ in range(N)]

row_sum = [0]*N
col_sum = [0]*M
for i in range(N) :
  for j in range(M) :
    if i == 0 or i == N-1:
      col_sum[j] += nums[i][j]
    else :
      col_sum[j] += nums[i][j]*2
    if j == 0 or j == M-1:
      row_sum[i] += nums[i][j]
    else :
      row_sum[i] += nums[i][j]*2

ans = orig = row_sum[0] + row_sum[-1] + sum(row_sum[1:-1]) * 2
for sums in [row_sum, col_sum] :
  try :
    minval = min(sums[1:-1])
    maxval = max(sums[0], sums[-1])
    if ans < orig - minval + maxval :
      ans = orig - minval + maxval
  except :
    continue
print(ans)print('hello world')