글 읽기 - 파이썬 시간 초과가 나오네요. 효율적으로 바꿀 수 있는 부분은 어디일까요?

gyjinro 3년 전 0

최악의 경우가 6,500만번 정도 연산이라고 생각해서 시간내 될 거라고 생각했는데 시간초과가 됐습니다. ㅠㅠ

아직 시간 관리가 서툴러서 어떤 부분을 바꾸면 좋을지 조언을 좀 부탁드립니다.

import sys
N, M, B = map(int, sys.stdin.readline().split())
start = time.time()
# 블록 맵
blocks = []
# 층 당 블록 수
lpb = N * M
# 인벤의 블록 제한에 따른 증층 한계
raising_limit = B / lpb

# 평균 위치를 시작점!
average_level = 0

lt_dict = {}


def level_time(level):
    if level in lt_dict:
        return lt_dict[level]
    else:
        time = 0
        for x in blocks:
            for y in x:
                gab = y - level
                time += gab * 2 if gab > 0 else gab * -1
        lt_dict[level] = time
        return time


for _ in range(N):
    a = list(map(int, sys.stdin.readline().split()))
    average_level += sum(a)/lpb
    blocks.append(a)

# 탐색 시작점 = 블록의 평균 값
level = int(average_level)
level_limit = average_level + raising_limit
# 탐색 방향 잡기(위? 아래?)
if level + 1 > level_limit or level_time(level) < level_time(level + 1):
    head = -1
else:
    head = 1

# 다음 탐색 할 층
temp_level = level + head

# 조건에 맞는 값을 찾을 때까지 반복 탐색 진행
# 조건 1. 0 또는 상승 한계에 도달한다.
# 시간이 다시 증가하는 변곡점을 찾는다.
while 0 <= temp_level <= level_limit and level_time(level) >= level_time(temp_level):
    level = temp_level
    temp_level += 1

print(lt_dict[level], level)

djm03178 3년 전 0

파이썬으로 6500만이면 1초 내에 실행되기는 어렵습니다. 잘해야 1천만 정도가 가능합니다. PyPy로는 조금 나을 수도 있습니다.

gyjinro 3년 전 0

아 그렇군요.. 답변 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 시간 초과가 나오네요. 효율적으로 바꿀 수 있는 부분은 어디일까요?

gyjinro 3년 전 0

djm03178 3년 전 0

gyjinro 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말