[백준] 16971번 배열 B의 값

문제 설명

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

문제 풀이

• 분류를 나누자면 브루트 포스로 풀이하였다.
• 중요한 점은 배열B의 합을 구할때 A배열에서 각 칸이 더해지는 횟수이다.

  • 배열의 4개 꼭지점 : 1번씩 더해짐
  • 배열의 4개의 변 : 2번씩 더해짐
  • 배열의 나머지 칸 : 4번씩 더해짐

• 따라서 총합을 늘릴 수 있는 경우는 배열의 4개의 변(외곽 row 또는 col)을 중앙 row 및 col과 교환해주는 경우이다.
• 각 케이스를 고려하여 문제를 풀이하였다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N, M;
    public static int[][] map;
    public static int[][] row; //특정 row값의 합 0: 중앙 로우 일때 1: 사이드 로우 일때
    public static int[][] col; //특정 col값의 합 0: 중앙 칼럼 일때 1: 사이드 칼럼 일때

    //최적의 두 행 or 두 열 바꿔서 최대로 늘어날 수 있는 값을 리턴
    //최소값인 row나 col을 첫번째나 마지막 row, col이랑 바꿔줌
    public static int solve() {
        //행 교환 세팅
        int rowDiff = -1, row1, row2 = 0;
        if (N > 2) {
            //row1 결정 (중간 row로 변경 했을 때 증가값이 큰 것)
            if (row[0][0] - row[0][1] < row[N - 1][0] - row[N - 1][1]) row1 = N - 1;
            else row1 = 0;
            //row2 결정 (사이드 row로 변경 했을 떄 손실값이 가장 작은 것)
            int minValue = Integer.MAX_VALUE;
            for (int i = 1; i < N - 1; i++) {
                if (row[i][0] - row[i][1] < minValue) {
                    minValue = row[i][0] - row[i][1];
                    row2 = i;
                }
            }
            rowDiff = row[row1][0] - row[row1][1] - (row[row2][0] - row[row2][1]);
        }
        //열 교환 세팅
        int colDiff = -1, col1, col2 = 0;
        if (M > 2) {
            //col1 결정
            if (col[0][0] - col[0][1] < col[M - 1][0] - col[M - 1][1]) col1 = M - 1;
            else col1 = 0;
            //col2 결정
            int minValue = Integer.MAX_VALUE;
            for (int i = 1; i < M - 1; i++) {
                if (col[i][0] - col[i][1] < minValue) {
                    minValue = col[i][0] - col[i][1];
                    col2 = i;
                }
            }
            colDiff = col[col1][0] - col[col1][1] - (col[col2][0] - col[col2][1]);
        }

        if (rowDiff < 0 && colDiff < 0) return 0;
        if (rowDiff > colDiff) return rowDiff;
        return colDiff;
    }

    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        row = new int[N][2];
        col = new int[M][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (i == 0 || i == N-1) {
                    col[j][0] += map[i][j] * 2;
                    col[j][1] += map[i][j];
                } else {
                    col[j][0] += map[i][j] * 4;
                    col[j][1] += map[i][j] * 2;

                }
                if (j == 0 || j == M-1) {
                    row[i][0] += map[i][j] * 2;
                    row[i][1] += map[i][j];
                } else {
                    row[i][0] += map[i][j] * 4;
                    row[i][1] += map[i][j] * 2;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        //최대값 계산
        int result = 0;
        for (int i = 0; i < N; i++) {
            if (i == 0 || i == N-1) result += row[i][1];
            else result += row[i][0];
        }
        bw.write((result + solve()) + "\n");
        bw.flush();
        bw.close();
        bw.close();
    }
}