[백준 18111] 마인크래프트 (Python)

처음 이 문제를 보고 일단 모든 층 ( 0 <= floar <= 256 ) 일때 time을 계산해봐야겠다는 생각이 들었다.

 

1. 임의의 층보다 더 높을 때

-> 블록을 제거하여 인벤토리에 넣은 시간은 2초이기 때문에

- time += 높은 만큼 * 2

- b += 높은 만큼

 

2. 임의의 층보다 더 낮을 때

-> 블록을 쌓는데 걸리는 시간이 1초이고 인벤토리에 충분한 블록이 없으면 더이상 못 쌓기 때문에

- 인벤토리 값이 낮은 만큼보다 크거나 같을때 time += 낮은 만큼

- 인벤토리 값이 낮은 만큼보다 크거나 같을때 b -= 낮은 만큼

- 인벤토리 값이 낮은 만큼보다 클때 break

 

첫 코드

import sys

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

ground = []
for _ in range(n):
    ground.append(list(map(int, input().split())))

def solution(ground, b):
    result_t = sys.maxsize + 1
    result_f = -1
    for f in range(257):
        time = 0
        invent = b
        a = 0
        for i in range(n):
            for j in range(m):
                diff = ground[i][j] - f
                if diff > 0:
                    time += diff * 2
                    invent += diff
                elif diff < 0:
                    if invent >= -diff:
                        time -= diff
                        invent += diff
                    else: break

        if time <= result_t:
            if result_f < f:
                result_f = f
            result_t = time
            
    print(result_t, result_f)

solution(ground, b)

 

이 코드를 실행 했을때 pypy3 기준 틀렸다고 뜬다 ...

 

반례와 모든 예시 테스트케이스가 통과가 되는데 대체 왜 틀렸지 ...? 라고 생각을 했는데

 

이 부분에서 틀린거였다 .. !!!

나는 칸을 순서대로 층과 비교하면서 더 낮은 경우에는 인벤토리에서 블록을 꺼내 쌓아줘야 하는데 블록 개수가 층과의 차이보다 작으면 쌓을 수가 없으니 break을 한 뒤 다음 for문이 돌도록 하였는데

 

이 뒷 순서의 칸에서 충분히 블록을 인벤토리에 넣어서 앞순서 칸에 블록을 쌓을 수 있다는 사실을 깨달았다....!!!

꼭 순서대로 평탄화를 하라는 조건이 없으니 모든 반복문 이후에 (총 인벤토리에 들어가는 블록 개수 > 쌓아야하는 블록 개수) 가 맞는지만 확인하면 되는 것이었다 !

 

두 번째 코드

import sys

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

ground = []
for _ in range(n):
    ground.append(list(map(int, input().split())))

def solution(ground, b):
    result_t = sys.maxsize + 1
    result_f = -1
    for f in range(257):
        time = 0
        invent = b
        a = 0
        for i in range(n):
            for j in range(m):
                diff = ground[i][j] - f
                if diff > 0:
                    time += diff * 2
                    invent += diff
                elif diff < 0:
                    time -= diff
                    invent += diff

        if invent >=0 and time <= result_t:
            if result_f < f:
                result_f = f
            result_t = time
            
    print(result_t, result_f)

solution(ground, b)

그렇게 코드를 수정하였지만 이번에는 시간초과가 뜨는 ... ㅜㅜ

 

이 부분은 다른 사람의 코드를 참고하여 이유를 발견하게 되었다.

하나의 임의의 층으로 평탄화를 한 뒤에 인벤토리에 남아있는 블록의 수가 음수이면 더 이상 더 높은 층은 조사해보지 않아도 되는 것이다 !

 

이미 평탄화로 필요한 블록의 개수가 인벤토리에 넣은 블록의 개수보다 더 큰데 평탄화 층이 더 높아질 수록 필요한 블록의 개수는 더 많아지기 때문에 어차피 평탄화가 불가능한 것 !

 

최종 코드

import sys

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

ground = []
max_f = 0
min_f = 257
for _ in range(n):
    a = list(map(int, input().split()))
    ground.append(a)
    max_a = max(a)
    min_a  = min(a)
    if max_a > max_f:
        max_f = max_a
    if min_a < min_f:
        min_f = min_a


def solution(ground, b, max_f, min_f):
    result_t = sys.maxsize + 1
    result_f = -1
    for f in range(min_f, max_f + 1):
        time = 0
        invent = b
        a = 0
        for i in range(n):
            for j in range(m):
                diff = ground[i][j] - f
                if diff > 0:
                    time += diff * 2
                    invent += diff
                elif diff < 0:
                    time -= diff
                    invent += diff
        if invent < 0: break
        elif time <= result_t:
            if result_f < f:
                result_f = f
            result_t = time
            
    print(result_t, result_f)
    
solution(ground, b, max_f, min_f)

쨘 이렇게 pypy3 기준 맞았습니다!가 떴다 !!

 

그런데 여전히 python3 기준으로는 시간초과이다 ..

다른 분의 글을 봤을 때 ground를 리스트가 아닌 딕셔너리 타입으로 문제를 풀면 시간이 훨씬 줄어든다고 한다 !

 

python3도 통과가 되게끔 도전해보고 싶었지만.. 오픽도 공부해야하기 때문에 다음에 시간이 되면 도전해보는걸루 !

 

다음은 내가 얼마나 많이 실패했는지 보여준다 

흙흙,,, 차라리 틀렸습니다가 더 낫지 시간초과는 .. 뭐가 문제인지 찾아내는게 너무 어렵다

이 또한 계속 풀다보면 감이 잡히려나 ..?

 

요즘 1일 1백준 하고 있으니 실력 향상되길 기대중 !

다음주부터는 항해 99 코테 스터디도 시작되니 열심히 해보자 ! 아자아자 홧팅 !