[구현] (3-6) 격자판의 합 : 한 iteration 최대한 써먹기

문제:  격자판 최대합

5*5 격자판에 오른쪽과 같이 숫자가 적혀있습니다.

N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가 장 큰 합을 출력합니다.

<입력설명>
첫 줄에 자연수 N이 주어진다.(1<=N<=50)
두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는다.

<출력설명>
최대합을 출력합니다.

입력예제
5
10 13 10 12 15

12 39 30 23 11

11 25 50 53 15

19 27 29 37 27

19 13 30 13 19

출력예제

155

 

처음 생각은 이러했다.

#row
for i in range(N):
    row = sum(table[i])
    max 갱신
#column
for i in range(N):
    column = sum(table[j][i] for j in range(N))
    max 갱신
#왼쪽위에서 시자하는 대각선
across1 = sum(table[i][i] for i in range(N))
max 갱신

#왼쪽아래에서 시작하는 대각선
across2 = sum(table[i][(N-1)-i] for i in range(N))
max 갱신

 

그러나 이러한 형식으로 절반쯤 작성하였을때에, 조금 더 효율적인 코드를 짜고싶었고 다음과 같은 형식으로 변경해보았다.

(모두 같은 i를 iteration으로 돌기에 가능함을 판단)

 

for i in range(N):
    # 매 iteration에서 
    # row, column 하나씩 나온다
    row = sum(table[i])
    column = sum(table[j][i] for j in range(N))
    max(row, column, max_sum)
    
    # 두 대각선의 element가 하나씩 매 iteration에서 나옴
    across1 += (table[i][i])
    across2 += table[i][(N-1)-i]
# 두 대각선의 합 완성
max(across1, across2, max_sum)

 

i에 대한 for문을 가로, 세로, 두 대각선에 모두 사용하면 연산량을 줄일 수있다.

big-O 시간복잡도는 위와 다르지 않겠으나, 이러한 아이디어 하나하나가 결국 빛을 발하는 날이 오지 않을까

 

최종 코드:

 

import sys
input = sys.stdin.readline

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

max_sum = 0

across1 = 0
across2 = 0

for i in range(N):
    # rows
    row = sum(table[i])
    #columns
    column = sum(table[j][i] for j in range(N))
    max_sum = max(row, column, max_sum)
    #two acrosses
    across1 += table[i][i]
    across2 += table[i][N-1-i]

max_sum = max(across1, across2, max_sum)
print(max_sum)