[C++] 백준 18111번 : 마인크래프트

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

하... 이 문제도 한 달 전에 푼 문제지만 다시 푸니까 또 틀렸다.

기억이 나는 문제인게, 처음 푼 당시에는 아이디어가 떠오르지 않아 답지를 봤었다..ㅜ

뭐 이번엔 아이디어는 떠올랐지만, 좀 푸는데 오래걸렸다....ㅜㅜ

1. 문제 정의

마인크래프트

- 1 * 1 * 1 크기의 블록들로 이뤄진 3차원 세계에서 
- 집터 : N(세로) * M(가로)
- 왼쪽 위의 좌표 : (0,0)


- 집터 내의 땅의 높이를 일정하게
1. (i, j)의 가장 위에 있는 블록을 제거해 인벤토리에 넣기 : 2초
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓기 : 1초
- 집터 아래에 빈 공간 없음
- 인벤토리에서만 블록을 가져올 수 있음
- 땅의 높이는 256블록을 초과할 수 없음, 음수 불가

출력 : 작업 최소 시간, 땅의 높이 (같은 시간이면 최대 높이)

2. 풀이 과정

- 이진탐색
최소 : 0, 최대 : 1
(1 + 0 ) / 2 = 0  -> 0으로 높이를 맞춘다.
1 * 2 = 2

최소 : 63, 최대 : 64
(64 + 63 ) /2 = 63 -> 63으로 높이를 맞춘다.
11 * 2 = 22  
만약 인벤토리에서 블록을 꺼내올 수 있다면
최소 -> 64
(64 + 64) / 2 = 64
1*1 = 1


최소 : 0, 최대  : 256 ->
(0 + 256 ) / 2 = 128
필요한 블록 수(required) : 64 -  board[i][j]
만약 B < required -> 블록을 채울 수 없음 -> 블록을 얻어야 하므로 최대 높이가 줄어드는 방향으로
만약 B >= required -> 블록을 채을 수 있음 -> 채우는 게 더 빠른 작업

2 2 99999
1 64
1 1
최소 : 1 최대 64
(64 + 1) / 2 = 32
(31 * 1) + (32 * 2) + (31 * 1) + (31 * 1) = 32 * 5 = 160

만약 B >= required -> 블록을 채울 수 있음 -> 높이가 더 높아도 됨
최소: 33 최대: 64
(33 + 64) / 2 = 97/2 = 48
47 + (16 * 2) + 47 + 47 = 141 + 36 = 178

재귀,, 백트래킹? 

요약하면,, 이진 탐색을 통해서 답을 찾아 나가야 하는데, 그 과정이 재귀인가? 뭐 이런 생각을 했다.

3. 정답 코드 ver. 2진탐색

#include <bits/stdc++.h>
using namespace std;

int n, m, b;
int board[500][500];
int height = INT_MAX;

int minTime = INT_MAX;

void solution(int left, int right)
{

    if (left <= right)
    {
        int currHeight = (left + right) / 2;
        // cout << currHeight << endl;
        int required = 0;   // 요구되는 블록 수
        int extraBlock = 0; // 새로 얻게되는 블록 수

        // 블록 분류하기
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (currHeight > board[i][j])
                {
                    required += (currHeight - board[i][j]);
                }
                else
                {
                    extraBlock += (board[i][j] - currHeight);
                }
            }
        }

        // 가용 블록 < 요구되는 블록 -> 불가능한 경우
        // 가용 블록 >= 요구되는 블록 -> 시간 계산하기
        if (b + extraBlock < required)
        {
            // 블록을 얻어야 하므로 최대 높이가 줄어드는 방향으로
            solution(left, currHeight - 1);
        }
        else
        {

            int currTime = (2 * extraBlock) + required;
            if (currTime <= minTime)
            {
                if (currTime == minTime)
                {
                    height = max(currHeight, height);
                }
                else
                {
                    height = currHeight;
                }
                minTime = currTime;
            }
            solution(left, currHeight - 1);
            solution(currHeight + 1, right);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> b;
    int left = INT_MAX, right = -1;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> board[i][j];
            left = min(left, board[i][j]);
            right = max(right, board[i][j]);
        }
    }

    solution(left, right);
    cout << minTime << " " << height << endl;
}

4. 다른 아이디어 : 그리디 완탐

음.. 과거 흔적을 보니 완탐으로 풀었다..
그래 그게 더 단순하긴 하네요.
하지만 이분탐색으로 푸니까 더 빠르죠?