18111 마인크래프트

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

#dp

18111번: 마인크래프트

 

#답안지 본 문제

#울고싶다.

 

#18111

from sys import stdin

#스탠다드 인풋

input=stdin.readline

#input을 스탠다드 인풋으로 바꿔줍니다

def solution():

    n,m,b=map(int,input().split())

#n,m,b 입력

    height_list=dict()

#각 블록들을 사전에 정리합니다

#이 생각을 할 수 있는 이유는 사실 블록의 위치는 상관없고 블록의 개수만 상관 있기 때문입니다. 일단 블록을 쫙 모아서 상자에 넣는다고 생각하자

    for i in range(n):

        for j in map(int,input().split()):

            if j in height_list:

                height_list[j]+=1

            else:

                height_list[j]=1

#어렵지 않게 생각해볼 수 있다

#다 돌려서 보는데 만약 있으면 1올려주고 없으면 만들어준다.

 

    total_block=0

    '''

    기본적인 생각 돌리기 전에

    이제 인벤토리양이랑 블록양 신경 안쓰고 싶으면

    총 블록 구해서 돌릴때 총블록 넘는거 안 구한다는 마인드

 

    돌리는건 시간문제에서 초를 for문으로 만들어서 끉어서 생각하는거랑 같다고 보면 된다.

    높이로 끉어서 최소값일때 리턴 0 m로 시작한다고 보면 됨.

    '''

    for i in height_list:

        total_block+=i*height_list[i]

#그럴라면 총 블록 필요 key값은 블록높이 value는 블록 개수

 

    max_height=0

    min_time=1001*n*m

#최소시간 최대높이 설정

 

    for i in range(257):

#i를 257m까지 올린다

        

        if n*m*i <= total_block+b:

#만약 현재 높이로 고르게 했을때 필요한 블록 양이 전체 블록+인벤토리에 있는 블록 보다 작아야 돌아감

#없으면 그냥 성립이 안됨 상자에 있는 블록보다 쓰여지는 블록이 더 많다는 소리

            time=0

           

            for block in height_list.keys():

                if block<i:

                    time+=(i-block)*height_list[block]

                else:

                    time+=(block-i)*2*height_list[block]

#시간으로 바로 대입해버리자.

#block은 높이이다. 상자에서 블록을 꺼내서 높이만 비교 지금보는거보다 높으면 짜르고 낮으면 넣고

#이거 할때의 시간차이도 적용해주고

 

            if time<=min_time:

               

                min_time=time

               

                max_height=i

 #시간을 비교해서 되면 이제 최대 높이 최소 시간 갱신

 

    print(min_time,max_height)

               

if __name__=='__main__':

    solution()