섹션 2. Array - 9. 격자판 최대합

📌 문제 설명

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

---

💡 해결 방법

• 각 행과 열, 두 대각선의 합을 구하면서 동시에 최대값을 갱신하여 최종 최대 합을 구합니다.

---

💻 코드 구현 (Java)

package partArray;

import java.util.Scanner;

public class Problem9 {
	public int solution(int num, int[][] arr) {
		int answer = 0;
		int sum1, sum2;
		
		for(int i = 0; i < num; i++) {
			sum1 = sum2 = 0;
			for(int j = 0; j < num; 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 < num; i++) {
			sum1 += arr[i][i];
			sum2 += arr[i][num - 1 - i];
		}
		answer = Math.max(answer, sum1);
		answer = Math.max(answer, sum2); 	
		
		return answer;
	}
	
	public static void main(String[] args) {
		Problem9 T = new Problem9();
		Scanner kb = new Scanner(System.in);
		int num = kb.nextInt();
		int[][] arr = new int[num][num];
		for(int i = 0; i < num; i++) {
			for(int j = 0; j < num; j++) {
				arr[i][j] = kb.nextInt();
			}
		}
		System.out.print(T.solution(num, arr));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 행과 열의 합

for(int i = 0; i < num; i++) {
	sum1 = sum2 = 0;
	for(int j = 0; j < num; j++) {
		sum1 += arr[i][j]; // 행의 합
		sum2 += arr[j][i]; // 열의 합
	}
	answer = Math.max(answer, sum1);
	answer = Math.max(answer, sum2);
}

• 모든 행과 열의 합을 구해 최대값을 찾습니다.

2️⃣ 대각선의 합

sum1 = sum2 = 0;
for(int i = 0; i < num; i++) {
	sum1 += arr[i][i];             // 좌상단에서 우하단으로
	sum2 += arr[i][num - 1 - i];   // 우상단에서 좌하단으로
}
answer = Math.max(answer, sum1);
answer = Math.max(answer, sum2);

• 두 대각선의 합을 구하고 최대값을 찾습니다.

---

⏳ 시간 복잡도 분석

• 격자판의 모든 원소를 한 번씩 확인하므로 전체 시간 복잡도는 O(N²)입니다.

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

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