마인크래프트

• 지형 편집과 비슷한 문제처럼 보이지만 풀이는 완전히 다르다. 저 문제처럼 효율적으로 풀수 있는 방법이 없고, 그냥 브루트포스로 높이를 0으로 맞출때, 1로 맞출때, …, H로 맞출때 까지의 시간을 전부 구해서 최솟값을 찾는 방법밖에 없다. (H는 높이가 가장 높은 좌표의 높이)
  • H⇐256 이란 조건이 있어서 실행시간은 짧게 걸린다
• 높이를 h로 맞출때 걸리는 시간을 계산하는 방법은 구현 방식에 따라 효율성이 조금 차이난다
  • N*M개의 좌표에 대해서 각각 걸리는 시간을 따로따로 계산한다면 O(N*M) 가 걸리고, 이것은 시간 초과가 난다
  • 높이가 X인 좌표는 h로 맞출때 걸리는 시간이 동일하다. 따라서 높이별로 해당되는 좌표의 갯수를 카운트해둔 뒤에, H개의 높이들에 대해서 h로 바꿀때 걸리는 시간을 구한뒤 거기에 그 높이에 해당하는 좌표의 갯수를 곱해서 더하는 식으로 처리하면 O(H)가 되고 쉽게 풀린다
  • 좀더 시간복잡도를 단축하려면, 모든 좌표를 h로 맞출때 걸리는 시간 T(h)를 T(h-1)로부터 계산하는 방법이 있다. 높이가 h보다 낮은 좌표의 갯수와 h보다 높은 좌표의 갯수를 갱신해서 유지하면, 그것으로부터 계산할수가 있고 이러면 O(1)에 계산 가능하다.
• 각 높이에 대해서 O(1)에 계산한다면 H개의 높이에 대해서 최솟값을 찾는데에는 O(H)가 걸린다. 처음 입력을 받는데 걸리는 시간 O(N*M)을 포함하면 총 시간복잡도는 O(N*M + H)

"""Solution code for "BOJ 18111. 마인크래프트".

- Problem link: https://www.acmicpc.net/problem/18111
- Solution link: http://www.teferi.net/ps/problems/boj/18111
"""

import collections


def main():
    # pylint: disable=unused-variable
    N, M, B = [int(x) for x in input().split()]
    count_by_height = collections.Counter()
    for _ in range(N):
        heights = [int(x) for x in input().split()]
        count_by_height.update(heights)

    all_block_count = sum(
        height * count for height, count in count_by_height.items())
    max_height = max(count_by_height)

    shorter_count = 0
    taller_count = N * M - count_by_height[0]
    inven = B + all_block_count
    min_time = time = all_block_count * 2
    height_at_min_time = 0
    for height in range(1, max_height + 1):
        shorter_count += count_by_height[height - 1]
        inven -= taller_count + shorter_count
        if inven < 0:
            break
        time -= taller_count * 2 - shorter_count
        taller_count -= count_by_height[height]
        if time <= min_time:
            min_time, height_at_min_time = time, height

    print(min_time, height_at_min_time)


if __name__ == '__main__':
    main()