18111 - 마인크래프트, python에서의 elif와 else 속도 차이

안녕하세요. 꼬동입니다.

 

최근 solved.ac를 통해서 문제를 하나씩 부수고 있는데요.

 

굉장히 좋은 문제를 한 번 들고 와봤습니다.

 

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

18111번: 마인크래프트

쉽다고 생각했지만..

추가 시간이 없기에, C로 푸는게 유리하나, 맥북이라 C를 못 돌려서... 흑흑

---

문제를 처음 봤을 땐, 굉장히 쉽게 생각했습니다.

 

왜냐면, 256 * 500 * 500 해도 1억이 안넘으니, 충분히 1초 안에 들어올 수 있다고 생각을 했죠.

 

근데 이게 뭐람

?

어떤 짓을 해도 시간 초과가 뜨더군요

 

시간 초과 났던 코드는 다음과 같습니다.

 

import sys

input = sys.stdin.readline

def check(h, b):
    global N, M, m_re
    t = 0

    for n in range(N):
        for m in range(M):
            if m_re < t:
                return -1
            if h < MAT[n][m]:
                t += (MAT[n][m] - h) * 2
                b += MAT[n][m] - h
            elif h > MAT[n][m]:
                t += h - MAT[n][m]
                b -= h - MAT[n][m]

    if b < 0:
        return -1

    return t

N, M, B = map(int, input().split())
MAT = [list(map(int, input().split())) for n in range(N)]

m_re, h_re = float('inf'), 0
for h in range(257):
    t = check(h, B)
    if t >= 0 and m_re >= t:
        m_re = t
        h_re = h

print(m_re, h_re)

여러분이 코드를 보자마자 저기가 시간 초과 나겠군... 이라고 생각하신다면, 당신은 천재 짝짝

 

근데, 저는 죽어도 못 찾겠더라고요. 그래서 다른 사람이 짠 코드를 보다가... 응? 했던 부분이 있었는데요.

 

elif였습니다.

 

그래서 이걸 else로 바꿔보니..

 

import sys

input = sys.stdin.readline

def check(h, b):
    global N, M, m_re
    t = 0

    for n in range(N):
        for m in range(M):
            if m_re < t:
                return -1
            if h < MAT[n][m]:
                t += (MAT[n][m] - h) * 2
                b += MAT[n][m] - h
            else:
                t += h - MAT[n][m]
                b -= h - MAT[n][m]

    if b < 0:
        return -1

    return t

N, M, B = map(int, input().split())
MAT = [list(map(int, input().split())) for n in range(N)]

m_re, h_re = float('inf'), 0
for h in range(257):
    t = check(h, B)
    if t >= 0 and m_re >= t:
        m_re = t
        h_re = h

print(m_re, h_re)

모야

되네..?

 

else와 elif의 시간 속도가 이렇게 많이 차이 날 줄 몰랐는데, 궁금해서 한 번 찾아봤습니다.

 

https://stackoverflow.com/questions/17166074/most-efficient-way-of-making-an-if-elif-elif-else-statement-when-the-else-is-don

Most efficient way of making an if-elif-elif-else statement when the else is done the most?

이 글이 제가 겪은 문제에 해답이 될지는 모르겠는데, 어쨌든 elif의 속도가 굉장히 느리다는 것을 증명합니다.

 

어떻게 동작하는지 한 번 뜯어봐야 할거 같은데, 뜯어보죠.

 

import dis

def f1(a):
    if a > 0:
        return 1
    elif a < 0: # 저는 문제에서 0을 빼기 위해서 elif를 썼습니다.
        return 0

def f2(a):
    if a > 0:
        return 1
    else:
        return 0

dis.dis(f1)
dis.dis(f2)

 

이게 f1

이게 f2

이게 뭔 소리야

 

뭐... 위에 보면 8번의 연산을 더 한다는거 정도는 알 수 있는데요. 왜냐면, f1에서의 12번에서 20번 사이의 연산이 없기 때문입니다.

 

왜냐면, f1에서 첫 if문에서 elif로 POP_JUMP_IF_FALSE를 하기 때문이고, 여기서 연산이 한 번 더 이뤄지는거죠.

 

후..

---

뭔 이런 사소한걸로 시간초과를 시키지 하면서 문제 탓을 오지게 하고있었는데,

 

보니까, 이렇게 푸는 거 보다 더 좋은 방법이 있더라고요 ..?

 

그래서 제가 좋은 문제라고 들고 온건데,

 

저는 그 MATRIX에서 하나 하나 꺼내가면서 높이를 측정했는데, 그럴 필요없이, MATRIX에 존재하는 높이 별로 갯 수를 구해서, 한 꺼번에 계산을 할 수도 있더군요.

 

역시

 

문제는 잘 못이 없다. ^_^

import sys

input = sys.stdin.readline

N, M, B = map(int, input().split())
MAT = []
HEIS = [0 for _ in range(257)]
for n in range(N):
    T = list(map(int, input().split()))
    for m in range(M):
        HEIS[T[m]] += 1
    MAT.append(T)

m_res, h_res = float('inf'), 0
for h in range(257):
    p = 0
    m = 0
    for b in range(257):
        if h > b:
            p += (h - b) * HEIS[b]
        else:
            m += (b - h) * HEIS[b]
    inven = B + m - p
    if inven < 0:
        continue
    t = m * 2 + p
    if t <= m_res:
        m_res = t
        h_res = h

print(m_res, h_res)

---

이상 18111 - 마인크래프트, python에서의 elif와 else 속도 차이였습니다. ^_^