NxM 크기의 그리드가 주어지는 경우, 그 높이를 균일하게 맞춰 평평하게 만들어야 하는 문제입니다.

브루트 포스 형식의 문제로, 최소 층과 최대 층의 범위를 구하고 모든 층에 대해서 걸리는 시간을 체크합니다.

평평하게 만들 수 있고 가장 시간이 적게 걸리는 층을 찾습니다.

#include<iostream>
#include<vector>
#include<limits>

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	int N, M, B;
	std::cin >> N >> M >> B;

	std::vector<std::vector<int>> map;
	int top = -1;
	int bottom = 257;

	int l = std::numeric_limits<int>::max();
	int time = std::numeric_limits<int>::max();

	// make map
	for (int i = 0; i < N; i++)
	{
		std::vector<int> horizontal;
		for (int j = 0; j < M; j++)
		{
			int temp;
			std::cin >> temp;

			if (temp < bottom) bottom = temp;
			if (temp > top) top = temp;

			horizontal.push_back(temp);
		}
		map.push_back(horizontal);
	}

	// 모든 층에 대해서 평지를 만드는 데 걸리는 시간 계산
	for (int level = bottom; level <= top; level++)
	{
		int stack = 0;
		int remove = 0;

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (map[i][j] < level) // 현재 level보다 낮은 경우
					stack += level - map[i][j];
				else if (map[i][j] > level) // 현재 level보다 높은 경우
					remove += map[i][j] - level;
			}
		}

		if (stack <= remove + B) // 애초에 채워야 하는 블록 개수가 부족한 경우는 다른 층에서 고려됨
		{
			int calcT = stack + remove * 2;

			if (time >= calcT)
			{
				l = level;
				time = calcT;
			}

		}
	}

	std::cout << time << " " << l;

	return 0;
}

실패한 시도

중간값을 찾아 map에서 최대, 최소 위치를 아이템 개수를 고려하며 깎고 쌓는 과정을 반복했습니다. 결과 자체는 제대로 나왔지만 시간 초과 문제가 발생했습니다.

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

std::pair<int, int> FindTop(std::vector<std::vector<int>> map, int& value)
{
   std::pair<int, int> result;
   int topval = -1;

   for (int i = 0; i < map.size(); ++i)
   {
      for (int j = 0; j < map[i].size(); ++j)
      {
         if (map[i][j] > topval)
         {
            topval = map[i][j];
            result.first = i;
            result.second = j;
         }
      }
   }
   value = topval;
   return result;
}
std::pair<int, int> FindBottom(std::vector<std::vector<int>> map, int& value)
{
   std::pair<int, int> result;
   int bottomval = 257;

   for (int i = 0; i < map.size(); ++i)
   {
      for (int j = 0; j < map[i].size(); ++j)
      {
         if (map[i][j] < bottomval)
         {
            bottomval = map[i][j];
            result.first = i;
            result.second = j;
         }
      }
   }
   value = bottomval;
   return result;
}


int main()
{
   std::ios::sync_with_stdio(false);
   std::cin.tie(NULL);

   int N, M, B;

   std::cin >> N >> M >> B;

   std::vector<std::vector<int>> map;

   std::vector<std::pair<int, int>> numCnt;

   int top = -1;
   int bottom = 257;

   std::pair<int, int> topPos;
   std::pair<int, int> bottomPos;

   for (int i = 0; i < N; ++i)
   {
      std::vector<int> horizonVec;
      for (int j = 0; j < M; ++j)
      {
         int temp;
         std::cin >> temp;

         if (temp < bottom)
         {
            bottom = temp;
            bottomPos.first = i;
            bottomPos.second = j;
         }
         if (temp > top)
         {
            top = temp;
            topPos.first = i;
            topPos.second = j;
         }

         horizonVec.push_back(temp);
         
         bool exist = false;
         for (std::pair<int, int>& a : numCnt)
         {
            if (a.first == temp)
            {
               a.second++;
               exist = true;
               break;
            }
         }

         if (!exist)
            numCnt.push_back(std::pair<int, int>(temp, 1));
      }
      map.push_back(horizonVec);
   }

   std::sort(numCnt.begin(), numCnt.end(), [](const std::pair<int, int> a, const std::pair<int, int> b) {return a.second > b.second; });
   int middle = numCnt[0].first;

   int time = 0;
   while (top != middle || bottom != middle)
   {
      if (B <= 0)
      {
         int dist = top - middle;

         map[topPos.first][topPos.second] -= dist;
         topPos = FindTop(map, top);
         B += dist;
         time += 2 * dist;
      }
      else
      {
         if (bottom == middle)
         {
            int dist = top - middle;

            map[topPos.first][topPos.second] -= dist;
            topPos = FindTop(map, top);
            B += dist;
            time += 2 * dist;
         }
         else
         {
            map[bottomPos.first][bottomPos.second]++;
            bottomPos = FindBottom(map, bottom);
            B--;
            time++;
         }
      }
   }

   std::cout << time << " " << map[0][0];

   return 0;
}

해당 글을 참고해 문제를 해결했습니다.