자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Array_격자판 최대합)

 

https://cote.inflearn.com/contest/10/problem/02-09

OnlineJudge

 

(위의 링크는 인프런 로그인 후, 해당 강의를 사지 않으면 접속이 되지 않습니다)

 

9. 격자판 최대합

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

 

강의 풀이(Time: 218ms Memory: 31MB)

 2중 for문 하나로 행의합,열의합,대각선합 중에 최대값을 구하는걸 어떻게 해야할지 몰라서  강의를 봤다.

대간선의 합은 따로 for문 한개로 구하는 겨였다.

package Array.격자판_최대합;

import java.util.Scanner;

public class Main {
    public int solution(int n, int[][] array) {

        int answer = Integer.MIN_VALUE;
        // sum1은 행의 합, sum2는 열의 합
        int sum1, sum2;
        // 각 행과 열을 구해야하기 때문에 2중 for문
        for (int i = 0; i < n; i++) {
            sum1=sum2=0;
            for (int j = 0; j < n; j++) {
                // i가 0일때 0행의 합, 0열의 합
                // i가 1일때는 1행의 합, 1열의 합
                // 행이 고정되고 열이 막 도는 것이다.
                sum1+= array[i][j];
                // 열이 고정되고 행이 막 도는 것이다.
                sum2+= array[j][i];
            }
            // sum1이나 sum2가 answer기존값보다 크다면 최대값이 들어간다
            answer = Math.max(answer, sum1);
            answer = Math.max(answer, sum2);

        }

        // 대각선
        sum1 = sum2 = 0;
        for (int i = 0; i < n ; i++) {
            sum1 += array[i][i];
            sum2 += array[i][n-i-1];
            answer = Math.max(answer, sum1);
            answer = Math.max(answer, sum2);
        }
        return answer;
    }

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