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

문제

There are pizza boxes all of which have the same dimensions. The boxes are stacked in piles, forming a three- dimensional grid where the heights are all different. The view from front shows the height of the tallest pile in each column, the view from the side shows the height of the tallest pile in each row.

What is the maximum number of pizza boxes we can remove without changing the front and side views? In the following example, Figure I.2 shows the solution of Figure I.1(a) case. In Figure I.1(a) and Figure I.2, each number (height) represents the number of boxes stacked.

Figure I.1. (a) Grid of heights and (b) the corresponding views.

Figure I.2. Grid of heights after removing boxes.

Your task is to compute the maximum number of pizza boxes that can be removed without changing the original front and side views.

입력

Your program is to read from standard input. The input contains two integers, n and m (1 ≤ n, m ≤ 1,000), the number of rows and columns in the grid, respectively. Each of the following n lines contain m integers, the number of pizza boxes (heights) in the corresponding row. All heights are between 0 and 109 inclusive and the heights are all different.

출력

Your program is to write to standard output. Print exactly one line for the input. The line should contain the maximum number of pizza boxes that can be removed without changing the original views.

예제 입출력

• 예제 입력 1

4 4
1 2 4 6
16 9 13 11
5 10 8 15
12 14 7 3

• 예제 출력 1

72

• 예제 입력 2

3 5
1 11 25 20 23
17 2 16 21 15
10 3 12 24 22

• 예제 출력 2

101

Solution

#include <iostream>
#include <set>
#define MAX 1001

using namespace std;

int MATRIX[MAX][MAX];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    set<int> maxSet;
    int sum = 0;
    for(int i = 1; i <= N; i++){
        int inputValue;
        int maxValue = 0;
        for(int j = 1; j <= M; j++) {
            cin >> inputValue;
            sum += inputValue;
            MATRIX[i][j] = inputValue;
            maxValue = max(inputValue, maxValue);
        }
        maxSet.insert(maxValue);
    }

    for(int i = 1; i <= M; i++){
        int maxValue = 0;
        for(int j = 1; j <= N; j++){
            maxValue = max(maxValue, MATRIX[j][i]);
        }
        maxSet.insert(maxValue);
    }
    for(auto i : maxSet){
        sum -= i;
    }
    cout << sum << '\n';
}

간단하다. 입력받으면서 한 행의 최댓값을 갱신하고 나중에 열의 최댓값을 갱신한다.

각 행, 열 기준의 최댓값만 빼고 나머진 전부 빼버리면 된다. 그러려면 여러가지 방법이 있겠지만, 중복 데이터 저장을 피하기 위해 set을 활용했다.

입력받으면서 우선 모든 값을 전부 더해버리면 편하다. 나중에 각 행, 열 기준의 최댓값들만 모두 합쳐서 빼버리면 될테니까. 더 고급지게 짤 수도 있겠지만 뭐 방법이야 다양하게 있을거고 일단 내 생각엔 저게 최선이겠지 싶었다. (필자는 머리가 정말 나쁘다...)