[BaekJoon] 18111 마인크래프트

[출처 : https://www.acmicpc.net/problem/18111]

import sys
n, m, b = map(int,sys.stdin.readline().rstrip().split())

groundHeight = [list(map(int,sys.stdin.readline().rstrip().split())) for i in range(n)]

#numOfH ={i:0 for i in range(257)}
linearGround = []

minH = 256
maxH = 0

for raw in groundHeight :
    if min(raw) < minH:
        minH = min(raw)
    elif max(raw) > maxH:
        maxH = max(raw)     
    for h in raw:
        linearGround.append(h)

linearGround.sort(reverse=True)

result = (-1, -1)

while minH <= maxH :
    totalT = 0
    tempB = b
    flag = True
    for h in linearGround:
        if h > minH or tempB == 0:
            totalT += (h - minH) * 2
            tempB += (h - minH)
        elif h < minH and tempB >= (minH-h):
            totalT += (minH - h)
            tempB -= (minH - h)
        elif h == minH:
            continue
        else : 
            flag = False 
            break    

    if tempB >= 0 and flag:
        if result[0] == -1 :
            result = (totalT, minH)
        elif result[0] > totalT :
            result = (totalT, minH)
        elif result[0] == totalT and result[1] < minH:
            result = (totalT, minH)

    minH += 1

print(result[0], result[1])​

 

▶ 문제풀이

 

1. 초기 입력데이터를 받아 각각의 위치마다의 높이 값을 선형데이터로 변환 + 높이의 최대값 최소값을 구함 

2. 선형데이터 정렬(내림차순)

3. 최소 높이부터 최대 높이까지 순회하면서 각 경우의 소요시간 및 높이를 구함

    3-1) 첫번째 if문에 의해 높이(h)가 현재 순회하는 높이(minH)보다 큰경우에 대해 처리함 이때 블록의 개수는 0일 수 있음(블록이 없으면 블록을 파내야 하므로)

    3-2) 두번째 elif문에 의해 높이(h)가 현재 순회하는 높이(minH)보다 작은 경우에 대해 처리 이때에는 현재 가진 블록의 수가 해당 빈칸을 메울 만큼 가지고 있어야함

    3-3) 세번째 elif문에의해 현재 순회하는 높이(minH)와 같은경우 continue

    3-4) 마지막 else문에 의해 각각의 경우가 아닌경우에는 flag를 False로 하고 break

4. 문제에 조건에 의해 시간이 최소화되는 것을 우선으로 하며 만일 시간소요가 같은 경우 높이가 더 높은 것으로 현재 결과를 수정하는 코드 

5. 결과 반환

 

★★★ 초기 python3로 채점시 시간초과 오류가 발생

=> 확인결과 pypy 와 python3 가 각각 사용하는 경우가 다르고 해당 문제의 경우 메모리 제한이 굉장히 널널한 편이였기에 pypy를 통해 문제해결을 할 수 있었음 

[pypy vs python 참고사이트]