[알고리즘] 격차판 최대합

문제

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

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

▣ 입력예제
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

function solution(arr) {
        let answer = Number.MIN_SAFE_INTEGER;
        let len = arr.length;
        let sum1 = 0;
        let sum2 = 0;
        for (let i = 0; i < len; i++) {
          sum1 = 0;
          sum2 = 0;
          for (let j = 0; j < len; j++) {
            sum1 += arr[i][j];
            sum2 += arr[j][i];
          }
          answer = Math.max(answer, sum1, sum2);
        }
        sum1 = 0;
        sum2 = 0;
        for (let i = 0; i < len; i++) {
          sum1 += arr[i][i];
          sum2 += arr[i][len - i - 1];
        }
        answer = Math.max(answer, sum1, sum2);
        return answer;
      }

      let arr = [
        [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],
      ];
      console.log(solution(arr));

설명

우선 행과 열의 합을 구하기 위하여 배열의 반복문을 돌린다.
sum1이 행의합, sum2가 열의합으로
행의합을 구하기 위해선 이중반복문으로 arr[i][j]를 반복시켜야한다.
예를들어 i의 첫번째 반복문에선 arr[0][0] arr[0][1] arr[0][2] 이 순서대로 배열의 length값 까지 반복이 돌게되는데 그러면 첫번째 행의 합이 구해지게 된다. (계속 반복하게 되면 마지막 행의 합까지 반복이 된다)

그렇다면 열의 합은 어떻게 구할까?
열의합도 행의합처럼 같은 개념을 사용하면된다.
arr[j][i]를 돌리면 된다. 그러면 arr[0][0] arr[1][0] arr[2][0] 이런식으로 쭉 반복문이 돌면서 열의 합이 만들어지게 된다.

한번의 행 반복문이 종료하게되면 그 행의 인덱스가 해당하는 행과 열의 합. 즉 sum1과 sum2이 구해지게 되는데, 그때 Math객체의 max메서드를 활용하여 최대값을 구한다. 그리고 다 끝나면 sum1과 sum2는 0으로 초기화시켜줘야하고 다시 반복을 돌려줘야한다.

이러한 과정이 모두 끝나면 모든 열과 행 합의 최대값이 구해지게 된다.

행과 열의 합 최대값 구하기가 끝나면 대각선으로 구해야한다.

대각선의 합은
arr[i][i] -> 왼쪽에서 오른쪽으로 내려가는 대각선
arr[i][len - i - 1] -> 오른쪽에서 왼쪽으로 내려가는 대각선
을 생각하고 반복문을 만들면 된다.

마지막에 다시 한번 구해진 모든 값의 최대값을 구해주면 된다.