[Inflearn] 자바 알고리즘 문제풀이 #02-09 9. 격자판 최대합

문제

설명

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

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

 

입력 

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

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

 

출력 

최대합을 출력합니다.

 

 

 

내 풀이

import java.util.Scanner;

public class Main2_9 {
    public int Solution(int n, int[][] arr) {
        int max=Integer.MIN_VALUE;
        int[] sum = new int[2*n+2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum[i] += arr[i][j]; // 각 행의 합
                sum[i+n] += arr[j][i]; // 각 열의 합
                if(i==j) sum[n+n] += arr[i][i]; // 우측 하향 대각선의 합
                sum[n+n+1] = arr[i][n-(i+1)]; // 좌측 하향 대각선의 합
            }
        }
        for (int i = 0; i < sum.length; i++) {
            if(sum[i]>max) max=sum[i];
        }
        return max;
    }

    public static void main(String[] args) {
        Main2_9 T = new Main2_9();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[][] arr = new int[num][num];
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        System.out.println(T.Solution(num, arr));
    }
}

5*5 격자판을 예시로 들자면,

sum[0]~sum[4] 까지 n개는 각 행의 합, sum[5]~sum[9] 까지 n개는 각 열의 합, sum[10]은 우하향 대각선의 합, sum[11]은 좌하향 대각선의 합을 넣고 sum 배열 (각 행의 합, 각 열의 합, 두 대각선의 합) 중 가 장 큰 합을 출력한다.

(n이 바뀌더라도 sum배열을 2*n+2만큼 만들어주기 때문에 비슷한 원리로 적용된다)

우하향 대각선의 합, 좌하향 대각선의 합은 i변수로만 접근하기 때문에 선생님 풀이랑 비슷하다고 볼 수 있을 것 같다.

내가 혼자 풀어내서 너무 기분 좋았음 !

 

 

 

선생님 풀이

import java.util.Scanner;

public class Main2_9 {
    public int Solution(int n, int[][] arr) {
        int answer = Integer.MIN_VALUE;
        int sum1, sum2;
        for (int i = 0; i < n; i++) {
            sum1=sum2=0; // sum1 : 행의 합, sum2 : 열의 합
            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; // sum1 : 우측 하향 대각선의 합, sum2 : 좌측 하향 대각선의 합
        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;
    }

    public static void main(String[] args) {
        Main2_9 T = new Main2_9();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[][] arr = new int[num][num];
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        System.out.println(T.Solution(num, arr));
    }
}

 

 

 

결과