문제 링크
문제
티어: 골드 3
알고리즘: 누적합, 그리디, 구현
크기가 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
풀이
구하고자 하는 것은 배열 A에서 교환을 최대 1번 수행해서 만들 수 있는 배열 B의 값의 최댓값을 구하는 것이다.
배열의 값은 배열의 모든 원소를 합한 값이다.
일단 완전 탐색이 되는지 확인했다. N,M <= 1000 이기 때문에 딱봐도 불가능하다.
그러면 스왑을 통해 배열 B의 값을 최대로 하려면 어떻게 해야 할까?
먼저, 배열 A에서 배열 B가 어떻게 만들어지는지 한 번 그려보자,
그러면 그 특징을 바로 알 수 있다.
배열 A에서 배열 B로 만들 때 특징을 정리하자면,
- A의 직각 부분은 한 번만 더해진다.
- A의 사이드, 위아래 행 열은 직각을 제외하고 모든 요소가 두 번씩 더해진다.
- 그 외 모든 부분은 네 번씩 더해진다.
그러면 값을 최대로 하기 위해서 사이드 열이나, 위아래 행 중 큰 값을 선택해서 내부에 있는 열이나 행 중 가장 작은 값과 교체하면 된다.
여기서 행, 열의 값은 내부에 있는 열이나 행이라고 가정하고, 계산한다.
예를 들어
위아래 중 선택한 행이 1 4 6 7라고 했을 때 1 2 + 4 4 + 6 4 + 7 2의 값을 가진다.
이렇게 가정해야 내부 행과 정확히 비교할 수 있기 때문이다.
시간 복잡도는 O(N * M)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int[][] A;
static int N, M; //N은 행, M은 열
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N][M];
for(int i=0; i<N; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
A[i][j] = Integer.parseInt(st2.nextToken());
}
}
if(N == 2 && M == 2) {
System.out.println(calArrB(A));
}
System.out.println(answer());
}
static int answer() {
return Math.max(calRow(), calCol());
}
static int calRow() {
int[] row = new int[M];
for(int i=0; i<M; i++) {
int v = 0;
for(int j=0; j<N; j++) {
if(j == 0 || j == N-1) {
//사이드인 경우
v += A[j][i] * 2;
} else {
v += A[j][i] * 4;
}
}
row[i] = v;
}
int ind = -1;
if(row[0] <= row[M - 1]) {
ind = M-1;
} else {
ind = 0;
}
int minInd = -1;
for(int i=1; i<M-1; i++) {
if(row[i] < row[ind]) {
//작은 것 중에 가장 작은 값을 구해야 됨
if(minInd == -1 || row[i] < row[minInd]) {
//최초거나 더 작은 값이면
minInd = i;
}
}
}
if(minInd == -1) {
return calArrB(A);
}
int[][] copyA = deepCopyArr(A);
swap(true, copyA, ind, minInd);
return calArrB(copyA);
}
static int calCol() {
int[] col = new int[N];
for(int i=0; i<N; i++) {
int v = 0;
for(int j=0; j<M; j++) {
if(j == 0 || j == M-1) {
v += A[i][j] * 2;
} else {
v += A[i][j] * 4;
}
}
col[i] = v;
}
int ind = -1;
if(col[0] <= col[N-1]) {
ind = N-1;
} else {
ind = 0;
}
int minInd = -1;
for(int i=1; i<N-1; i++) {
if(col[i] < col[ind]) {
if(minInd == -1 || col[i] < col[minInd]) {
minInd = i;
}
}
}
if(minInd == -1) {
return calArrB(A);
}
int[][] copyA = deepCopyArr(A);
swap(false, copyA, ind, minInd);
return calArrB(copyA);
}
static void swap(boolean isRow, int[][] arr, int ind1, int ind2) {
int tmp = -1;
if(isRow) {
for(int i=0; i<N; i++) {
tmp = arr[i][ind1];
arr[i][ind1] = arr[i][ind2];
arr[i][ind2] = tmp;
}
} else {
for(int i=0; i<M; i++) {
tmp = arr[ind1][i];
arr[ind1][i] = arr[ind2][i];
arr[ind2][i] = tmp;
}
}
}
static int[][] deepCopyArr(int[][] arr) {
int[][] result = new int[arr.length][arr[0].length];
for(int i=0; i<arr.length; i++) {
for(int j=0; j<arr[i].length; j++) {
result[i][j] = arr[i][j];
}
}
return result;
}
static int calArrB(int[][] arr) {
int result = 0;
for(int i=0; i<N - 1; i++) {
for(int j=0; j<M - 1; j++) {
result += (arr[i][j] + arr[i + 1][j] + arr[i][j + 1] + arr[i + 1][j + 1]);
}
}
return result;
}
}