18111. 마인크래프트

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

 

이해

• 평탄화가 가능한 높이에 대해 모든 경우의 수를 비교해가며 풀어야하는 문제이다.
• 문제를 읽어보면 알 수 있 듯, 높이에 대한 인덱스가 중요하지 않아 2차원 배열이 아닌 1차원 배열로 입력을 받아도 되고, Dictionary 형태로 받아도 된다.

구현

1. N*M 행렬을 높이에 대한 Dictionary로 정의
   • collections 내부 defaultdict를 활용
2. 높이에 대해 쌓을 블럭 수와 부술 블럭 수를 따로 저장하여 계산 식으로 풀이
   • 만들 수 있는가? 👉 (부술 블럭 수) + (최초 인벤토리 블럭 수) >= (쌓는 블럭 수)
   • 걸리는 시간 👉 (부술 블럭 수) + 2 * (쌓는 블럭 수)
3. 걸리는 최소 시간 저장 및 최소 시간 중복 시 최대 높이 비교

코드

# 18111 마인크래프트
import sys
from collections import defaultdict
input = sys.stdin.readline

# 평탄화를 할 수 있는지 체크
def check(candidate:defaultdict, h:int):
	# 파는 수, 쌓는 수
    mine, build = 0, 0
    for key, val in candidate.items():
    	# type Error 나는 이유(key 중 str 형태가 있나봄)
        key = int(key)
        # 만약 만드려는 높이가 아니라면
        if key != h:
            diff = abs(key - h) * val
            # 높이 차이 만큼 더해줌
            if key > h:
                mine += diff 
            else:
                build += diff 
    # 쌓으려는 블럭 수가 인벤토리에 없으면 -1, 아니면 걸린 시간 반환
    return -1 if mine+B <build else 2*mine+build


def solution():
	# 최소 시간과 높이 저장용
    min_t,ans =500*500*257+1,-1
    # 최소 ~ 최대까만 돌리면 알 수 있음(다른 경우는 최소시간을 가질 수 없음)
    for h in range(minh, maxh+1):
		# 시간 계산
        time = check(house, h)
        # -1이면 패스
        if time >= 0:
        	# 최소 시간 계산
            if min_t > time:
                min_t = time
                ans = h
            # 최소 시간이 여러 개면 높이가 가장 높은 것
            elif min_t == time:
                if ans < h:
                    ans = h
    return (min_t, ans)


if __name__ == "__main__":
    N, M, B = map(int, input().split())
    # dictionary 로 저장하면 최악의 경우가 500*500 -> 256번으로 줄음
    house = defaultdict(int)
    minh,maxh = 257, -1
    for _ in range(N):
        for j in list(map(int, input().split())):
            house[j] += 1            
            minh = min(minh, j)       
            maxh = max(maxh, j)       
    print(*solution())

 

참조

Defaultdict?

• Dictionary 를 만드는 dict 클래스의 서브 클래스
• Dictionary와 유사하지만 최초 선언할 필요 없이 사용 가능
• 최소 호출 시 미리 지정된 타입의 기본값으로 정의
• 예시

from collections import defaultdict

default_dict = defaultdict(int)
default_dict['key']

print(default_dict)

>> defaultdict(<class 'int'>, {'key': 0})