백준 18111 마인크래프트

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#include <iostream>
#include <algorithm>

int g_heightFreq[257] = {};
int g_numRows = 0;
int g_numCols = 0;
int g_numBlocks = 0;

int CalculateTime(int p_height)
{
    int time = 0;
    int numBlocks = g_numBlocks;

    for (int height = 0; height <= 256; ++height)
    {
        const int freq = g_heightFreq[height];
        int diff = height - p_height;

        // 제거
        if (diff > 0)
        {
            time += 2 * diff * freq;
            numBlocks += diff * freq;
        }
        // 설치
        else if (diff < 0)
        {
            time -= diff * freq;
            numBlocks += diff * freq;
        }
    }

    return (numBlocks < 0) ? -1 : time;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> g_numRows >> g_numCols >> g_numBlocks;
    int maxHeight = 0;
    int minHeight = 256;

    // 높이 정보 기록
    for (int i = 0; i < g_numRows * g_numCols; ++i)
    {
        int height;
        std::cin >> height;
        ++g_heightFreq[height];

        maxHeight = std::max(maxHeight, height);
        minHeight = std::min(minHeight, height);
    }

    int minTime = 500 * 500 * 256 * 2;
    int optimalHeight = 0;

    // 최소/최대 높이 범위의 땅 고르기 작업 시 걸리는 시간 계산
    for (int h = maxHeight; h >= minHeight; --h)
    {
        const int time = CalculateTime(h);

        // 블록이 부족한 경우
        if (time == -1)
        {
            continue;
        }
        // 기존 작업 시간보다 더 짧은 경우
        if (time < minTime)
        {
            minTime = time;
            optimalHeight = h;
        }
    }

    std::cout << minTime << " " << optimalHeight;

    return 0;
}