[JAVA] 격자판 최대합

출처 - 인프런

 

접근하기

 

행과 열로 이루어진 데이터는 십중팔구 2차원 배열을 의미하기 때문에

2차원 배열 및 이중 for문을 이용해서 풀면 되겠다고 생각했다.

 

TO-DO

1. 정수 N을 입력받아, N행 N열의 2차원 배열을 생성한다.

2. 2차원 배열 각각의 인덱스에 원소값을 입력한다.

3. 각 행, 각 열, 각 대각선( \ 방향 & / 방향) 의 합을 구해서 최댓값인지 비교한다.

 

그림 설명

 

5행 5열의 2차원 배열

 

먼저, 각 행의 합을 구하고자 할 때는

 

1행의 합 : [0][0] + [0][1] + [0][2] + [0][3] + [0][4]

2행의 합 :[1][0] + [1][1] + [1][2] + [1][3] + [1][4]

3행의 합 : ...

4행의 합 : ...

5행의 합 : ...

 

이렇게 되니까 이중 for문을 이용해서 코드를 구현하면 되겠다.

 

// 최대값 초기화
int max = Integer.MIN_VALUE;

// 합
int sum = 0;

for(int i = 0; i < N; i++) {
 for(int j = 0; j < N; j++) {
  sum += arr[i][j];
 }
 max = Math.max(sum, max);
 // 각 행의 합 계산이 끝났으면 sum을 다시 0으로 초기화
 sum = 0;
}

 

이런식으로 각 행의 합, 각 열의 합, 대각선의 합을 구한 뒤, max 값과 비교하면 되겠다.

 

 

코드

 

import java.util.Scanner;
  
public class Main {
	public static void main(String[] args) {
		Scanner sc  = new Scanner(System.in);
		int sum = 0;
		int max = 0;
		
		int N = sc.nextInt();
		
		int[][] iArr = new int[N][N];
		
		for(int i =0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				iArr[i][j] = sc.nextInt();
			}
		}
		
		// 가로의 합
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				sum += iArr[i][j];
			}
			max = Math.max(max, sum);
			sum = 0;
		}
		
		// 세로의 합
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				sum += iArr[j][i];
			}
			max = Math.max(max, sum);
			sum = 0;
		}
		
		// 대각선(\)의 합
		for(int i = 0; i < N; i++) {
			for(int j = i; j <= i; j++) {
				sum += iArr[i][j];
			}
		}
		
		max = Math.max(max, sum);
		sum = 0;
		
		// 대각선(/)의 합
		int idx = N - 1;
		for(int i = 0; i < N; i++) {
			sum += iArr[i][idx];
			idx--;
		}
		
		max = Math.max(max, sum);
		sum = 0;
		
		System.out.println(max);
	}
}

 

리뷰

 

2차원 배열과 관련된 알고리즘 문제를 풀기 위해서는 2차원 배열에 관한 개념이 잘 잡혀 있어야한다.

개인적으로 2차원 배열에 관한 개념을 정립하는데에 큰 도움을 받은 것은 유튜브 남궁성 채널이다.

혹시라도 2차원 배열만 보면 손이 벌벌 떨리고 눈물부터 난다면 유튜브 영상을 보고 개념을 다잡는것을 추천한다.