(알고리즘)격자판 최대합

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

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

입력

첫 줄에 자연수 N이 주어진다.(2<=N<=50)

두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는다.

출력

최대합을 출력합니다.

예시 입력 1 

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

155

코드

import java.util.Scanner;

public class Main {
    public int solution(int n, int[][] arr) {
        int result = Integer.MIN_VALUE;

        int sum = 0, crossSum = 0;

        for (int i = 0; i < n; i++) {
            int tmpSum1 = 0, tmpSum2 = 0;
            for (int j = 0; j < n; j++) {
                tmpSum1 += arr[i][j];
                tmpSum2 += arr[j][i];

                if (sum < Math.max(tmpSum1, tmpSum2)) {
                    sum = Math.max(tmpSum1, tmpSum2);
                }
            }
        }
        int tmpCsum1 = 0, tmpCsum2 = 0;
        for (int i = 0; i < n; i++) {
            tmpCsum1 += arr[i][i];
            tmpCsum2 += arr[i][n - 1 - i];
        }

        crossSum = Math.max(tmpCsum1, tmpCsum2);


        result = Math.max(sum, crossSum);
        return result;
    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        Main T = new Main();

        int n = in.nextInt();
        int[][] arr = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = in.nextInt();
            }
        }

        System.out.print(T.solution(n, arr));
    }
}

간단 설명

for (int i = 0; i < n; i++) {
    int tmpSum1 = 0, tmpSum2 = 0;
    for (int j = 0; j < n; j++) {
        tmpSum1 += arr[i][j];
        tmpSum2 += arr[j][i];

        if (sum < Math.max(tmpSum1, tmpSum2)) {
            sum = Math.max(tmpSum1, tmpSum2);
        }
    }
}

n번째 즉 배열의 길이만큼 돌면서 i번째의 행의 합과 열의 합을 구한다. 

 

즉 i가 0이면 0번째 행의 합과 0번째의 열의 합을 각각 구해서 두 수를 비교한 후 기존의 sum보다 크면 sum의 값을 행과 열의 합 중 큰 값으로 바꿔준다. 

 

int tmpCsum1 = 0, tmpCsum2 = 0;
for (int i = 0; i < n; i++) {
    tmpCsum1 += arr[i][i];
    tmpCsum2 += arr[i][n - 1 - i];
}

crossSum = Math.max(tmpCsum1, tmpCsum2);

이 부분은 대각선의 합을 구하는 부분으로 for문이 한번만 돌면 된다. 그리고 각 대각선 중 끝에서부터 시작해서 내려오는 대각선은 n - 1 - i로 구할 수 있다 

 

각 대각선의 합을 구한후 비교한 다음 기존에 행과 열의 합에서 나온 가장 큰 값과 비교하여 result를 반환하면 문제 해결!