BOJ 14754, Pizza Boxes

ACM-ICPC 2017 Nationalwide Internet 예선에서 나왔던 문제입니다.

나왔던 문제들 중 가장 쉬웠던 문제입니다.

문제는 피자박스가 다음과 같이 쌓여있을 때, 앞에서 본 모양과 옆에서 본 모양을 유지한 채로, 최대한 피자박스를 많이 치우면 몇 개나 치울 수 있는지를 찾는 것입니다.

 단, 피자박스의 높이는 모두 유일하다고 문제에 나와있습니다. 이 부분을 주의해서 읽지 않으면 피자박스의 높이가 같을 때 예외처리를 해야한다는 생각에 시간을 날릴 수 있습니다.

The boxes are stacked in piles, forming a three- dimensional grid where the heights are all different. 

해법은, Side에서 관찰할 때 가장 높은 피자박스를 모두 체크하고

Front에서 관찰할 때 가장 높은 피자박스를 모두 체크한 다음, 전체 피자 박스 수에서 체크된 피자박스 수를 빼주면 됩니다.

예제를 풀어봅시다.

피자박스가

4 4

1 2 4 6

16 9 13 11

5 10 8 15

12 14 7 3

과 같은 입력으로 주어졌습니다.

위에 그려둔 것처럼, 피자박스의 위치를 체크할 배열을 하나 더 만들어 둔 뒤에 2중 for문을 통해 차례로 체크한 다음, 각 방향마다 최대 높이를 갖는 곳을 표시해줍니다. 그리고 마지막에 2중 포문으로 Pizza Box의 정보를 담는 배열을 순회하면서 체크 전용 배열에 체크가 되어있다면? 더하지 않고, 체크가 되어있지 않은 경우엔 더해줍니다.

이렇게 문제를 해결하면, O(nm)의 시간복잡도를 가지게 되고, n,m이 모두 1000 이하의 정수이니 제한 시간 안에 충분히 문제를 해결할 수 있습니다.

소스코드는 다음과 같습니다.

이 문제를 풀면서 가장 주의하셔야 할 점은, 피자박스의 최대 높이가 10^9, 10억이라는 조건입니다. 이 경우엔, 최악의 경우 피자 박스를 3개만 더하더라도 signed int의 범위 (2^31)을 넘어가버리죠. 그래서 long long을 써야합니다.

빈번하게 실수하시는 부분이니, 앞으로는 모든 문제에 대해(메모리 제한이 심각하지 않는 한도에서) 모두 long long자료형을 쓰는 습관을 들이도록 합시다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
typedef long long LL;
 
LL map[1001][1001] = { 0, };
bool check[1001][1001] = { false, };
 
int main() {
    LL n, m;
    LL answer = 0;
    scanf("%lld %lld", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%lld", &map[i][j]);
        }
    }
 
    //Row
    for (int i = 0; i < n; i++) {
        int maxval = -1;
        int maxpos = -1;
        for (int j = 0; j < m; j++) {
            if (map[i][j] >= maxval) {
                maxpos = j;
                maxval = map[i][j];
            }
        }
        for (int j = 0; j < m; j++) {
            if (j == maxpos) check[i][j] = true;
        }
    }
 
    //Col
    for (int i = 0; i < m; i++) {
        int maxval = -1;
        int maxpos = -1;
        for (int j = 0; j < n; j++) {
            if (map[j][i] >= maxval) {
                maxpos = j;
                maxval = map[j][i];
            }
        }
        for (int j = 0; j < n; j++) {
            if (j == maxpos) check[j][i] = true;
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            answer += check[i][j] ? 0 : map[i][j];
        }
    }
 
    printf("%lld", answer);
    return 0;
}