백준 16971 배열 B의 값

문제링크

https://www.acmicpc.net/problem/16971

문제

풀이

배열 B의 배열의 값을 위해 배열 A의 원소가 몇번 사용되는지를 카운트 해주었다.

이 표를 통해 배열 A의 중간에 있는 행 또는 열끼리는 아무리 교환하더라도 배열 B의 배열의 값은 변하지 않는것을 확인할 수 있다.
따라서 배열 A의 첫번째 or 마지막 행열과 두번째~마지막-1 번째 행열을 교환 하는 경우를 모두 확인하여 값을 구해주었다.

코드

#include <iostream>
using namespace std;
int n, m;
int A[1001][1001];
int sum_g[1001], sum_s[1001];
int total, ans;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> A[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		int temp = 0;
		for (int j = 0; j < m; j++) {
			temp += A[i][j] * 4;
		}
		temp -= A[i][0] * 2;
		temp -= A[i][m - 1] * 2;
		if (i == 0 || i == n - 1) temp /= 2;
		sum_g[i] = temp;
		total += temp;
	}

	for (int i = 0; i < m; i++) {
		int temp = 0;
		for (int j = 0; j < n; j++) {
			temp += A[j][i] * 4;
		}
		temp -= A[0][i] * 2;
		temp -= A[n-1][i] * 2;
		if (i == 0 || i == m - 1) temp /= 2;
		sum_s[i] = temp;
	}
	
	ans = total;
	for (int i = 1; i < n-1; i++) {
		ans = max(ans, total + sum_g[0] - sum_g[i] / 2);
		ans = max(ans, total + sum_g[n - 1] - sum_g[i] / 2);
	}

	for (int i = 1; i < m-1; i++) {
		ans = max(ans, total + sum_s[0] - sum_s[i] / 2);
		ans = max(ans, total + sum_s[m - 1] - sum_s[i] / 2);
	}
	cout << ans;
}

후기

알고리즘 보다는 구현력이 필요한 문제였다.