[탐색 및 시뮬레이션] 파이썬 알고리즘 문제 2-6 "격자판 최대합"

격자판 최대합

[시간복잡도]

O(N²) : 이중 For문 작성

[공간복잡도]

O(N)

 

 

Problem

 

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

 

 

💯 Solution ①

: 튜터님의 코드와 굉장히 유사함

 

import sys
sys.stdin=open("input.txt","rt")
 
n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
# 최대값으로 잡을 max 설정
max=0
 
for i in range(n):
    sum1=0
    sum2=0
    for j in range(n):
        #sum1은 행의 합
        sum1+=a[i][j]
        #sum2는 열의 합
        sum2+=a[j][i]
    if max<sum1:
        max=sum1
    if max<sum2:
        max=sum2
 
#sum1,sum2 초기화
sum1=sum2=0
 
for i in range(n):
    # 왼쪽 대각선 합 : sum1
    sum1+=a[i][i]
    # 오른쪽 대각선 합 : sum2
    sum2+=a[i][n-1-i]
    if sum1>max:
        max=sum1
    if sum2>max:
        max=sum2
 
print(max)

(설명)

 

- 주어진 리스트를 받는 코드를 한줄로 작성한다.

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

: list(...)로 된 코드를 n번 반복하는 것을 a에 담는다.

 

- 최댓값으로 max를 설정한다.

- 반복문을 통해서 행과 열의 합을 구하는 코드를 작성하고 이를 max값과 비교해서 조건에 부합하다면 max에 담는다.

: 배열 안에 배열로 이루어진 이중배열을 가져온다.

 

- 반복문을 통해서 대각선의 합을 구하는 코드를 작성하고 이를 max값과 비교해서 조건에 부합하다면 max에 담는다.

: 여기서 포인트는! 오른쪽 대각선의 합을 구하는 코드에서 해당 값에 접근할 때 a[i][n-i-1]을 사용해서 접근한다.

 

- 출력양식을 지키기 위해서 max를 출력한다. 

💯 Solution ②

: Tutor's Code

 

import sys
sys.stdin=open("input.txt","r")
n=int(input())
 
# map() 코드가 한 줄을 읽음. 이를 리스트화까지 시킨 것
# 이를 n번 해야함. (n바퀴를 돈다)
a=[list(map(int,input().split())) for _ in range(n)]
#행과 열의 합 (최댓값 : largest)
largest=-2147000000
for i in range(n):
    # 행의합 sum1 / 열의합 sum2
    sum1=sum2=0
    for j in range(n):
        sum1+=a[i][j]
        # sum2의 열이 고정([i])
        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)

 

📚 참고