20.06.27 개발일지 - Pizza Boxes

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

14754번: Pizza Boxes

피자 박스가 N * M으로 쌓여 있습니다.

이 때 정면도와 측면도가 바뀌지 않도록 피자 박스를 제거 할 때, 최대 제거되는 피자 박스의 수를 구하는 문제입니다.

 

제가 선택한 방식은 다음과 같습니다.

0. 입력 받을 때 모든 상자 박스 높이의 합을 더합니다.

1. row 단위에서 최대 높이인 index를 vector에 저장합니다.

2. column 단위에서 최대 높이인 index를 vector에 저장합니다.

3. 단, 1과 2의 과정에서 vector 안에 동일한 index가 존재하면 저장하지 않습니다.

4. 저장된 indices의 상자 높이 만큼 연산된 상자 높이의 합에서 감산합니다.

 

처음 시도에는 오답을 받았습니다.

무엇이 문제인지 살펴보니, 상자 높이가 1B까지 입력 받고, 상자 뭉치 갯수는 1M개 만큼 입력을 받을 수 있었습니다.

입력값이 많을 경우, 상자 높이의 합이 int의 범위를 넘어설 수 있습니다.

그래서 상자 높이의 합을 int에서 unsigned long long으로 변경하였고, 정답을 맞출 수 있었습니다.

 

문제를 다 풀고 상자 순회를 한번에 해결할 수 있나 고민을 해보았습니다.

하지만 column과 row 단위에서 비교를 해 최대값을 뽑아야 하는 만큼,

둘 중 하나는 그 크기 만큼 최대값을 동시에 관리해야 했습니다.

이를 판단하는 것보다 차라리 순회를 두번 하는 것이 덜 복잡할 것 같습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int column = 0, row = 0, input = 0;
    unsigned long long output = 0;
    vector<vector<int>> tower;
    vector<vector<int>> LiveIndex;
    cin >> column >> row;
    for (int i = 0; i < column; ++i)
    {
        tower.push_back(vector<int>(row));
        for (int j = 0; j < row; ++j)
        {
            cin >> input;
            tower[i][j] = input;
            output += input;
        }
    }

    for (int i = 0; i < column; ++i)
    {
        int max = 0, cIndex = 0, rIndex = 0;
        for (int j = 0; j < row; ++j)
        {
            if (max < tower[i][j])
            {
                cIndex = i;
                rIndex = j;
                max = tower[i][j];
            }
        }
        auto temp = vector<int>{ cIndex, rIndex };
        if (find(LiveIndex.begin(), LiveIndex.end(), temp) == LiveIndex.end())
        {
            LiveIndex.push_back(temp);
        }
    }
    for (int i = 0; i < row; ++i)
    {
        int max = 0, cIndex = 0, rIndex = 0;
        for (int j = 0; j < column; ++j)
        {
            if (max < tower[j][i])
            {
                cIndex = j;
                rIndex = i;
                max = tower[j][i];
            }
        }
        auto temp = vector<int>{ cIndex, rIndex };
        if (find(LiveIndex.begin(), LiveIndex.end(), temp) == LiveIndex.end())
        {
            LiveIndex.push_back(temp);
        }
    }
    for (const auto& iter : LiveIndex)
    {
        output -= tower[iter[0]][iter[1]];
    }

    cout << output << endl;
    return 0;
}