[Algorithm] 격자판 최대합

격자판 최대합

설명

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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public int solution(int n, int[][] arr) {
        int answer = 0;
        int dia1=0, dia2=0;

        // 가로, 세로
        for (int i=0; i<n; i++) {
            int row=0, col=0;
            for (int j=0; j<n; j++) {
                row += arr[i][j];  // 각 행의 합
                col += arr[j][i];  // 각 열의 합
            }

            // 대각
            dia1 += arr[i][i];
            dia2 += arr[i][n-i-1];

            // 더 큰 값을 answer에 저장
            answer = Math.max(answer, row);
            answer = Math.max(answer, col);
            answer = Math.max(answer, dia1);
            answer = Math.max(answer, dia2);
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] numArr = new int[N][N];
        for (int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j=0; st.hasMoreTokens(); j++) {
                numArr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(T.solution(N, numArr));
    }
}

• 2차원 배열에서 각 행의 합, 각 열의 합, 대각선의 합 중 최대값을 구하는 문제였다.
• 이중 for문을 어떻게 순회할 지를 아는 것이 중요했다
  • 가로, 세로, 대각
• Math.max() 메소드를 통해 최대값을 쉽게 구할 수 있었다.

가로, 세로를 순회하는 것은 쉬웠는데, 대각을 어떻게 순회할지는 바로 떠오르지 않았다.
다양한 문제를 풀어보는 것이 중요한듯!