어흥
[백준 16971] 배열 B의 값 (C++) 본문
728x90
반응형
문제 링크: www.acmicpc.net/problem/16971
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;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 13422] 도둑 (C++) (0) | 2020.09.08 |
---|---|
[백준 14391] 종이 조각 (C++) (0) | 2020.09.05 |
[백준 1904] 01타일 (C++) (0) | 2020.08.30 |
[백준 16562] 친구비 (C++) (0) | 2020.08.27 |
[백준 1238] 파티 (C++) (0) | 2020.08.24 |
Comments