[SWEA] #1209 - Sum

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV13_BWKACUCFAYh 

SW Expert Academy

 

💡 문제

---

[설명]

다음 100X100의 2차원 배열이 주어질 때, 각 행의 합, 각 열의 합, 각 대각선의 합 중 최댓값을 구하는 프로그램을 작성하여라.

다음과 같은 5X5 배열에서 최댓값은 29이다.

[제약 사항]

1. 배열의 크기는 100X100으로 동일하다.

2. 각 행의 합은 integer 범위를 넘어가지 않는다.

3. 동일한 최댓값이 있을 경우, 하나의 값만 출력한다.

 

💡 아이디어

---

1. 행의 합

행의 합을 구하기 위해서는 2중 for문을 사용해 한 행을 읽어 나가면서 더해주면 구할 수 있다.

배열의 크기가 100이므로 행의 합도 총 100개가 나오는데, 매 행을 다 읽었을 때마다 대소 비교를 해주면 최댓값을 얻을 수 있다.

2. 열의 합

열의 합을 구하기 위해서는 1 - 100 인덱스를 가지는 배열을 우선 하나 만든다.

그리고 행을 읽어나가면서 각 인덱스에 해당하는 배열에 값을 계속해서 더해준다.

예를 들어, 배열 첫 번째 줄을 읽고 있다면 열의 합[1] = X, 열의 합[2] = Y ··· 의 형태이다.

배열의 마지막 줄까지 모두 읽고 나면 배열의 각 인덱스는 열의 합을 가지고 있을 것이다.

100개의 열의 합 중 최대를 구하면 그것이 열의 합 최댓값이 된다.

3. 대각선의 합

대각선의 합을 구하기 위해서는 행과 열의 관계를 잘 생각해보면 된다.

우선 오른쪽 아래로 뻗어가는 대각선은 배열 인덱스가 1로 시작한다고 가정했을 때 (1, 1), (2, 2) ···의 형태가 된다.

반면, 왼쪽 아래로 뻗어가는 대각선은 (1, 100), (2, 99), (3, 98) ···의 형태가 된다. 즉, 행과 열의 합이 101이 된다.

이 관계를 이용해 2개의 대각선에 대한 합을 구하고, 비교를 해주면 대각선의 합 최댓값을 구할 수 있다.

4. 최댓값 구하기

행의 합 최댓값, 최댓값, 열의 합 최댓값, 대각선의 합 최댓값을 구했으므로 이들을 다시 비교해주면 문제를 해결할 수 있다.

 

💡 소스코드

---

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.Scanner;

/*Sum*/
public class P_1209 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T, num;
		int ROW_MAX;// 행 최대값
		int COL_MAX;// 열 최대값
		int DIAG_MAX;// 대각선 최대값
		int FINAL_MAX;// 최종 최대값
		int ROW_SUM, DIAG_SUM1, DIAG_SUM2;// 행 합, 열 합, 대각선 합
		int[] COL_SUM = new int[101];// 각 열의 합

		for (int test_case = 1; test_case <= 10; test_case++) {
			T = sc.nextInt();

			/*----------------초기화------------------*/
			ROW_MAX = Integer.MIN_VALUE;
			COL_MAX = Integer.MIN_VALUE;
			ROW_SUM = 0;
			DIAG_MAX = Integer.MIN_VALUE;
			FINAL_MAX = 0;
			ROW_SUM = 0;
			DIAG_SUM1 = 0;
			DIAG_SUM2 = 0;
			Arrays.fill(COL_SUM, 0);
			/*---------------------------------------*/

			for (int i = 1; i <= 100; i++) {
				for (int j = 1; j <= 100; j++) {
					num = sc.nextInt();

					ROW_SUM += num;// 현재 행의 합

					COL_SUM[j] += num;// 첫 열부터 마지막 열까지 계속 더함

					if (i == j)// 오른쪽 아래 대각선 합
						DIAG_SUM1 += num;

					if (i + j == 101)// 왼쪽 아래 대각선 합
						DIAG_SUM2 += num;
				}
				if (ROW_SUM > ROW_MAX)// 현재 행의 합과 행의 최대값 비교
					ROW_MAX = ROW_SUM;

				ROW_SUM = 0;
			}

			// 대각선 최대값 구하기
			DIAG_MAX = Math.max(DIAG_SUM1, DIAG_SUM2);

			// 각 열의 합 정렬 후 열의 최대값 구하기
			Arrays.sort(COL_SUM);
			COL_MAX = COL_SUM[100];

			// 최종 최대값 구하기
			FINAL_MAX = Math.max(ROW_MAX, Math.max(COL_MAX, DIAG_MAX));

			System.out.println("#" + T + " " + FINAL_MAX);
		}
	}
}

 

💡 결과

---

100X100에 해당하는 배열을 처음부터 끝까지 탐색하기 때문에 메모리나 실행시간이 꽤 많이 들었다.

시간을 줄일 수 있는 효율적인 방법이 있을 것 같지만, 나는 떠올리진 못 했다...

다음에 기회가 된다면 이 문제를 다시 효율적으로 풀어보고 싶다.