[Algorithm/Java] 알고리즘 자바 격자판 최대합 (코딩테스트, Array, 배열, 행렬 합 최대값 구하기)

---

1. 문제 설명

• 설명 : 5*5 격자판에 아래롸 같이 숫자가 적혀있습니다. N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가장 큰 합을 출력합니다.
• 입력 : 첫 줄에 자연수 N이 주어진다.(2<=N<=50) 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는다.
• 출력 : 최대합을 출력합니다.

 

2. 문제 코드 및 풀이 설명

import java.util.Scanner;

public class GridMaximumSum {
  public static void main(String[] args) {
    GridMaximumSum T = new GridMaximumSum();
    Scanner kb = new Scanner(System.in);
    int n = kb.nextInt();
    int[][] arr = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        arr[i][j] = kb.nextInt();
      }
    }
    System.out.println(T.solution(arr, n));
  }

  // 해결방법
  // 입력받은 행렬에서 행의 값을 더한 값, 열의 값을 더한 값, 대각선을 더한 값을 비교
  // 가장 큰 것을 출력
  public int solution(int[][] arr, int n) {
    int answer = 0;
    int sum1, sum2;
    for (int i = 0; i < n; i++) {
      sum1 = sum2 = 0; // 합을 초기화
      for (int j = 0; j < n; j++) {
        sum1 += arr[i][j]; // 같은 행에 있는 값의 합
        sum2 += arr[j][i]; // 같은 열에 있는 값의 합
      }
      // 더 큰 값 집어넣기
      answer = Math.max(answer, sum1);
      answer = Math.max(answer, sum2);
    }
    sum1 = sum2 = 0;
    for (int i = 0; i < n; i++) {
      sum1 += arr[i][i]; // 왼쪽 위에서 오른쪽 아래로 대각선의 합
      sum2 += arr[i][n - i - 1]; // 왼쪽 아래에서 오른쪽 위로 대각선의 합
    }
    answer = Math.max(answer, sum1);
    answer = Math.max(answer, sum2);

    return answer;
  }
}

 

3. 출력 예시

입력
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

출력
155

 

---

위의 내용은 인프런에서 수강할 수 있는 김태원님의 자바 알고리즘 문제풀이 강의를 바탕으로 공부한 내용을 정리한 내용입니다!

https://inf.run/iAi6

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의