18111 - 마인크래프트

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

18111번: 마인크래프트

Python3 으로 제출했을 때 시간 초과 떠서 Brute force 말고 다른 알고리즘을 사용해야하나 고민한 짤 1

Python3 으로 제출했을 때 시간 초과 떠서 Brute force 말고 다른 알고리즘을 사용해야하나 고민한 짤 2

 

- Brute force

 

import sys
input = sys.stdin.readline

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

minh, maxh = 256, 0
for _ in range(n):
    x = list(map(int, input().split()))
    a.append(x)

    if max(x) > maxh:
        maxh = max(x)
    if min(x) < minh:
        minh = min(x)

mint, ansh = int(1e9), 0
for i in range(minh, maxh+1):
    temp_b = b
    s = 0
    for x in range(n):
        for y in range(m):
            s += (i-a[x][y] if i-a[x][y]>0 else 2*(a[x][y]-i))
            temp_b -= (i-a[x][y])

    if temp_b < 0:
        continue

    if mint >= s:
        mint = s
        ansh = i

print(mint, ansh)

 

최솟값부터 최댓값까지 모든 좌표를 순회하며 최솟값 / 블럭 초과 여부를 계산하면 되는 간단한 브루트 포스

 

 

...지만 Python3이 느린 인터프리터 언어라 같은 코드를 사용함에도 불구하고 시간 초과가 떴다.

나는 내 코드에 문제가 있는줄 알고 위에 보이는 것처럼 좀 어려운 매개 변수 탐색인가? 하고 풀었는데, 도저히 안풀려서 백준 질문칸에 가니까 Pypy3로 제출하면 된다는 말에...

 

완전히 같은 607B짜리 코드

진짜 됐었다..노얼탱스;;

 

Python3은 메모리가 적은 대신 많은 시간

Pypy3은 메모리가 많은 대신 적은 시간

 

한 번 배웠으니 다음에 이런 일은 없겠지..