파이썬 알고리즘-16 (탐색)격자판 최대합

jiffydev·2020년 8월 27일
0

Algorithm

목록 보기
17/92
post-thumbnail

16.격자판 최대합
5*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

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

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

▣ 출력설명
최대합을 출력합니다.

▣ 입력예제 1
5 1
0 13 10 12 15
12 39 30 23 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19

▣ 출력예제 1
155

내 코드

n=int(input())
lst=[[0]*n]*n
for i in range(n):
    lst[i]=list(map(int, input().split()))

tot=0

for i in lst:
    if sum(i)>tot:
        tot=sum(i)

for i in range(len(lst)):
    tmp=0
    for j in range(len(lst)):
        tmp+=lst[j][i]
    if tot<tmp:
        tot=tmp

for i in range(len(lst)):
    tmp=0
    for j in range(len(lst)):
        tmp+=lst[i][n-1-j]
    if tot<tmp:
        tot=tmp
tmp=0
for i in range(n):
    tmp+=lst[i][i]
if tot<tmp:
    tot=tmp

print(tot)

더하는 방식이 풀이와 약간 차이가 있었고, 특히 가로&세로, 양 대각선의 합을 각각 묶어서 반복문 두 개로 처리하지 못해서 아쉬움.

풀이

n=int(input())
a=[list(map(int, input().split())) for _ in range(n)]
largest=-2147000000
for i in range(n):
    sum1=sum2=0
    for j in range(n):
        sum1+=a[i][j]
        sum2+=a[j][i]
    if sum1>largest:
        largest=sum1
    if sum2>largest:
        largest=sum2
sum1=sum2=0
for i in range(n):
    sum1+=a[i][i]
    sum2+=a[i][n-i-1]
if sum1>largest:
    largest=sum1
if sum2>largest:
    largest=sum2
print(largest)

반성점

  • 반복문을 쓸데없이 많이 만들었다. 시간복잡도는 비슷하겠지만 더 직관적인 답을 도출해내야 한다.
  • 행렬에 대한 지식이 있음에도, 행이 a[i][j] 일 때 열이 a[j][i]임을 간과했다.

배운 것

  • 리스트를 반복해서 input해야 할 때는 lst=[list(map(int, input().split())) for _ in range(n)] 을 사용하면 코드 한 줄로 input이 가능하다.
profile
잘 & 열심히 살고싶다

0개의 댓글