Algorithm - 격자판 최대합

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[격자판 최대합]

 

5*5 격자판에 아래와 같이 숫자가 적혀있습니다.

5*5 격자판

 

N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가장 큰 합을 출력하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 50)

두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. (1 ≤ N < 100)

 

*출력 설명

최대합을 출력합니다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_16.txt', 'rt')

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-1-i]
    if sum1 > largest:
        largest = sum1
    if sum2 > largest:
        largest = sum2

print(largest)

# 출력 : 155

 

input_16.txt(입력)

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

 

 

중요내용

1. a = [list(map(int, input().split())) for _ in range(n)] 코드는 list(map(int, input().split())) 코드를 n번 반복 실행하겠다는 의미이다. (for문의 변수 자리에 변수 대신 언더바(_)를 사용하면 특정 변수없이 for문을 실행한다는 의미)
2. 첫 번째 for문에서 변수 sum1은 행의 합을 의미하고, 변수 sum2는 열의 합을 의미한다.
3. 두 번째 for문에서 변수 sum1과 sum2는 각 대각선의 합을 의미한다.
4. sum1 = sum2 = 0 코드는 반복문을 돌 때마다 두 변수를 0으로 초기화하겠다는 의미이다.
5. 첫 번재 for문에서 sum1 += a[i][j] 코드는 모든 행의 합, sum2 += a[j][i] 코드는 모든 열의 합을 의미한다.
6. 두 번재 for문에서 sum1 += a[i][i] 코드와 sum2 += a[i][n-1-i] 코드는 두 대각선의 합을 의미한다.