[알고리즘]격자판 최대합 구하기

❓ 격자판 최대합 구하기

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

[자바스크립트 알고리즘 문제풀이]

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

▣ 입력설명
첫 줄에 자연수 N이 주어진다.(1<=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

 

function solution(arr) {
    let answer = Number.MIN_SAFE_INTEGER;
    let n = arr.length;
    // sum1은 행의 합 sum2는 열의 합
    let sum1 = sum2 = 0;

    for (let i = 0; i < n; i++) {
        sum1 = sum2 = 0;
        for (let j = 0; j < n; j++) {
            sum1 += arr[i][j]
            sum2 += arr[j][i]
        }
        // answer와 sum1과 sum2의 최대값이 answer로 들어가게 된다.
        answer = Math.max(answer, sum1, sum2);
    }
    sum1 = sum2 = 0;
    for (let i = 0; i < n; i++) {
        // 왼쪽부터 오른쪽 아래 대각선으로 내려가는 합
        sum1 += arr[i][i]
        // 오른쪽부터 왼쪽 아래 대각선으로 내려가는 합
        sum2 += arr[i][n - 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));

 

 

💡 문제 풀이

answer에 최소값으로 초기화 해놓고 비교해가며 가장 큰 값과 비교하여 출력해낸다.

sum1은 격자판의 행의 합, sum2는 격자판의 열의 합이며 0으로 초기화 해둔다.

2중 for문을 돌며 행과 열의 합을 구하고 Math.max()메서드를 이용하여 그 중 가장 큰 값을 answer에 넣어준다.

마지막으로 대각선의 합을 구해야 하므로 for문을 사용하여 왼쪽에서 오른쪽 아래로 가는 대각선의 합, 오른쪽에서 왼쪽 아래로 가는 대각선의 합을 구해서 최대값을 Math.max()메서드로 구해주어 answer에 넣어준다