[Algorithm] 격자판 최대 합

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

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

입력 

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

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

출력 

최대합을 출력합니다.

 

풀이

아래와 같이 4가지 경우의 수를 따진다.

1. 가로 합 한 행씩 더해서 max 비교

2. 세로 합 한 열씩 더해서 max 비교

3. 좌측 상단에서 우측 하단으로 내려가는 대각

4. 우측 상단에서 좌측 하단으로 내려가는 대각

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] table = new int[n][n];

        // n * n 격자 만들기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                table[i][j] = sc.nextInt();
            }
        }

        System.out.println(solution(table, n));


    }

    static int solution(int[][] table, int n) {
        /**
         * 1. 가로합 비교
         * 2. 세로합 비교
         * 3. 대각합 비교 -> 두가지 경우의 수
         */

        int max = table[0][0];
        // 가로합 비교
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j < table.length; j++) {
                sum += table[i][j];
                if (sum > max) {
                    max = sum;
                }
            }
        }

        // 세로합 비교
        for (int j = 0; j < n; j++) {
            int sum = 0;
            for (int i = 0; i < n; i++) {
                sum += table[i][j];
                if (sum > max) {
                    max = sum;
                }
            }
        }

        // 대각합 비교
        // 1. 좌측 상단에서 우측하단으로 내려가는 대각 arr[i++][j++]
        int crossSumTemp = 0;
        for (int i = 0, j = 0; i < n; i++, j++) {
            crossSumTemp += table[i][j];
        }

        if (crossSumTemp > max) {
            max = crossSumTemp;
        }

        crossSumTemp = 0;

        // 2. 우측 상단에서 좌측 하단으로 내려가는 대각 arr[i++][j--]
        for (int i = 0, j = n - 1; i < n; i++, j--) {
            crossSumTemp += table[i][j];
        }

        if (crossSumTemp > max) {
            max = crossSumTemp;
        }

        return max;
    }
}

//  입력 제대로 됐는지 확인하는 출력 로직
//        for (int[] ints : table) {
//            for (int i : ints) {
//                System.out.print(i + " ");
//            }
//            System.out.println();
//        }