[백준 16971] 배열 B의 값 (C++)

문제 링크: www.acmicpc.net/problem/16971

16971번: 배열 B의 값

1. 주의할 점

- 각각의 원소가 배열 B가 만들어지기 위해 몇번 사용되는지 미리 계산한다. 다음과 같다

N = 10, M = 6의 경우, 배열 A의 각 원소가 더해지는 횟수

//1~M열
1 2 2 2 2 1			//1행
2 4 4 4 4 2
2 4 4 4 4 2
2 4 4 4 4 2
2 4 4 4 4 2
2 4 4 4 4 2			  ~
2 4 4 4 4 2
2 4 4 4 4 2
2 4 4 4 4 2
1 2 2 2 2 1			//N행

즉, 맨 위와 아래행(K번)은 나머지 행들에(2K) 비해 반번씩만 더해진다. 물론, 열도 앞선 규칙을 만족한다. 이를 이용한다

- 각 행/열에 대한 값을 미리 저장한다

- 2차 배열을 사용하지 않아도 된다

 

2. 구현

- 입력받을 때 Sum을 이용해 배열 B의 값을 미리 구한다. 또한, R[] 배열에는 각 행의 합을, C[] 배열에는 각 열의 합을 구해놓는다

- 위의 그림을 잘 보자. 행을 기준으로 2~N-1행끼리 바꾸면 B 배열의 합은 변하지 않는다. 열의 경우, 2~M-1열을 바꾸면 B 배열의 합이 바뀌지 않는다. 따라서 사이에 낀 행/열끼리 바꾸지 않도록 한다

- 가장자리에 있던 행/열과 안에 있던 행/열을 바꿀 경우, 안에 있던 행/열이 반으로 줄어든다(Ex. 2 4 4 2 -> 1 2 2 1). 반대로, 가장자리에 있던 행/열은 2배로 늘어난다.

- 위의 가정대로 식을 잘 세운다(밑의 코드에서 sum - r[i] + r[0]가 아닌 sum - r[i]/2 + r[0]인 이유가 여기에 있다)

 

#include <iostream>
#include <algorithm>
using namespace std;
int row, col, sum = 0, v;
int r[1000], c[1000];

void change() {
	int temp = -9876543210;
	for (int i = 1; i < row - 1; i++) {
		temp = max(temp, sum - r[i]/2 + r[0]);
		temp = max(temp, sum - r[i]/2 + r[row - 1]);
	}
	for (int i = 1; i < col - 1; i++) {
		temp = max(temp, sum - c[i]/2 + c[0]);
		temp = max(temp, sum - c[i]/2 + c[col-1]);
	}
	sum = max(sum, temp);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> row >> col;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			cin >> v;
			if (i == 0 || i == row - 1 || j==0 ||j==col-1) {
				if ((i == 0 && j == 0) || (i == 0 && j == col - 1) || (i == row - 1 && j == 0) || (i == row - 1 && j == col - 1)) {
					r[i] += v;
					c[j] += v;
					sum += v;
				}
				else {
					r[i] += (2 * v);
					c[j] += (2 * v);
					sum += (2 * v);
				}
			}
			else {
				r[i] += (4 * v);
				c[j] += (4 * v);
				sum += (4 * v);
			}
		}
	change();
	cout << sum;
	return 0;
}