문제
크기가 N×M인 배열 A가 있을 때, 다음과 같은 방법을 이용해서 크기가 (N-1)×(M-1)인 배열 B를 만들 수 있다.
- B[i][j] = A[i][j] + A[i+1][j] + A[i+1][j+1] + A[i][j+1] (1 ≤ i < N, 1 ≤ j < M)
배열의 값은 배열의 모든 원소를 합한 값이다.
배열 A에서 임의의 두 행이나 임의의 두 열의 위치를 교환할 수 있다. 배열 A에서 교환을 최대 1번 수행해서 만들 수 있는 배열 B의 값의 최댓값을 구해보자.
입력
첫째 줄에 배열 A의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 배열의 원소가 주어진다. 배열은 정수로만 이루어져 있다.
출력
만들 수 있는 배열 B의 값 중 최댓값을 출력한다.
제한
- 2 ≤ N, M ≤ 1,000
- -1,000 ≤ Ai,j ≤ 1,000
예제 입력 1
3 3
9 8 7
3 2 1
6 5 4예제 출력 1
92예제 입력 2
3 4
1 2 1 1
2 1 1 2
2 1 1 1예제 출력 2
34예제 입력 3
3 3
1 1 1
1 2 1
1 1 1예제 출력 3
20풀이
이 문제는 이 문제는 특별한 알고리즘을 이용해서 푸는 문제는 아니다. 그러나 주어진 조건과 문제 내용을 토대로 모든 경우의 수를 구하는 게 아닌 최적의 방법을 생각해서 풀어야 한다.
이러한 A배열이 있을 때 B배열의 값은 이 된다.
여기에서 4부분으로 나누어서 계산 할 수 있다.
i) 배열의 각 모서리는 한 번씩만 더해진다.
ii) 모서리를 제외한 0번 행과 열, N-1번 행, M-1번 열의 값들은 두 번씩 더해진다.
iii) 중간 행의 (0번, M-1번), 중간 열의 (0번, N-1번) 값들은 두 번씩 더해진다.
iiii) 중간 행,열의 나머지 값들은 네 번씩 더해진다.
위의 사항들로 생각해보면 중간의 행, 열끼리 위치를 교환해도 B 배열의 값은 변하지 않는다는 것을 유추할 수 있다.
그리고 조건에서 최대 1번 교환할 수 있기 때문에 0번 행과 열, N-1번 행, M-1번 열 중 하나와 중간의 행,열 중 하나를 교환하면 된다.
이 중 최대값을 구해야 하기 때문에 0번 행과 열, N-1번 행, M-1번 열 중 합이 가장 큰 하나와 중간의 행, 열 중 합이 가장 작은 행, 열 하나와 바꿔서 비교해보면 최대값을 구할 수 있다. 이때 초기 배열의 값과도 비교해봐야 한다.
import java.io.InputStreamReader;
import java.io.BufferedReader;
public class Main {
static int[][] A;
static int N;
static int M;
static int max;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
A = new int[N][M];
max = 0;
for(int i=0; i<N; i++) {
input = br.readLine().split(" ");
for(int j=0; j<M; j++)
A[i][j] = Integer.parseInt(input[j]);
}
for(int i=0; i<N-1; i++) {
for (int j=0; j<M-1; j++) {
max += (A[i][j] + A[i+1][j] + A[i+1][j+1] + A[i][j+1]);
}
}
if(N>2) {
int min_row = -1;
int sum_row = Integer.MAX_VALUE;
for(int i=1; i<N-1; i++) {
int sum = 0;
for (int j=0; j<M; j++) {
sum += A[i][j];
}
sum = 4*sum - 2*(A[i][0] + A[i][M-1]);
if(sum<sum_row) {
sum_row = sum;
min_row = i;
}
}
rotate(min_row, 0, true);
rotate(min_row, N-1, true);
}
if(M>2) {
int min_col = -1;
int sum_col = Integer.MAX_VALUE;
for(int j=1; j<M-1; j++) {
int sum = 0;
for (int i=0; i<N; i++) {
sum += A[i][j];
}
sum = 4*sum - 2*(A[0][j] + A[N-1][j]);
if(sum<sum_col) {
sum_col = sum;
min_col = j;
}
}
rotate(min_col, 0, false);
rotate(min_col, M-1, false);
}
System.out.println(max);
}
public static void rotate(int x, int y, boolean flag) {
int[][] a = new int[N][M];
if(flag) {
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(i==x)
a[y][j] = A[i][j];
else if(i==y)
a[x][j] = A[i][j];
else
a[i][j] = A[i][j];
}
}
}
else {
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(j==x)
a[i][y] = A[i][j];
else if(j==y)
a[i][x] = A[i][j];
else
a[i][j] = A[i][j];
}
}
}
int sum = 0;
for(int i=0; i<N-1; i++) {
for (int j=0; j<M-1; j++) {
sum += (a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i][j+1]);
}
}
max = Math.max(sum, max);
}
}