[문제풀이] 02-09. 격자판 최대합

인프런, 자바(Java) 알고리즘 문제풀이

Array(1, 2차원 배열) - 0209. 점수 계산

🗒️ 문제

🎈 나의 풀이

	private static int solution(int n, String[][] strings) {
        int answer = 0;
        int[] sum = new int[2*n + 2];

        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                // 가로, 세로합 구하기
                sum[i] += Integer.parseInt(strings[i][j]);
                sum[n + i] += Integer.parseInt(strings[j][i]);

                // 대각합 구하기
                if(i == j) sum[2 * n] += Integer.parseInt(strings[i][j]);
                else if(i + j == n - 1) sum[2 * n + 1] += Integer.parseInt(strings[i][j]);

                if(n % 2 != 0 && i == n/2 && j == n/2) sum[2 * n + 1] += Integer.parseInt(strings[i][j]);
            }
        }

        for(int i : sum) {
            answer = Math.max(i, answer);
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        String[][] strings = new String[n][];

        for(int i=0; i<n; i++) {
            strings[i] = sc.nextLine().split(" ");
        }

        System.out.println(solution(n, strings));
    }

🖍️ 강의 풀이

    public int solution(int n, int[][] arr){
		int answer=-2147000000;
		int sum1=0, sum2=0;
		for(int i=0; i<n; i++){
			sum1=sum2=0;
			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;
		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){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int[][] arr=new int[n][n];
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				arr[i][j]=kb.nextInt();
			}
		}
		System.out.print(T.solution(n, arr));
	}

💬 짚어가기

해당 문제는 2차원 배열을 통해 해결할 수 있다.
나의 풀이의 경우 2중 for문을 순회하며 격자판의 x, y 좌표를 이용해
배열에서 [x, y], [y, x]의 값을 누적 합하여 가로 세로 합을 구하고,
특정 좌표 조건 x == y, x + y = n - 1을 만족하는 대각 합을 구하였다.

강의에서는 마찬가지로 가로와 세로 합을 구하였고, 대각합의 경우
단일 for문을 한번 더 순회하며 [x, x], [x, n - x - 1]의 누적 합으로 구하였다.

또, 나의 풀이에서는 각 누적합을 보관하는 별도의 배열을 생성했지만,
강의에서는 매번 비교를 통해 최대 값만 저장하도록 했다.