글 읽기 - 파이썬 시간초과

pgh268400 2년 전 0

아래와 같이 작성했으나 시간초과가 뜹니다.

효율적으로 개선할 부분이 있을까요?

# m*n, b = 블럭갯수
#블록제거 = 2초, 블럭놓기 = 1초
import sys
#input = sys.stdin.readline().rstrip

mc_map = []
n,m,b = map(int, sys.stdin.readline().rstrip().split())
for i in range(n):
    lst = list(map(int, sys.stdin.readline().rstrip().split()))
    mc_map += lst

time_height = []

for i in range(0, 257): #브루트 포싱
    #리스트 처리 부분
    result = []
    target = i
    
    total = 0
    minimal = mc_map[0]
    for element in mc_map:
        result.append(element - target)
        total += element - target
        if(element < minimal):
            minimal = element

    time = 0
    if (total + b) < 0: #현재 땅에 튀어나와있는걸 전부 부수고 가지고 있는 블럭까지 합했는데도 채울 수 없다면
        for element in result:
            if(element != minimal):
                time += abs(element - minimal) * 2 #전부 부셔준다.
        #print(time, target + minimal)
        time_height.append((time, target + minimal))
    else: #채울 수 있다면
        for element in result:
            if (element > 0): #부셔야 하는 것 이라면
                time += abs(element) * 2 #부순다
            elif (element < 0): #채워야 하는 것이라면
                time += abs(element) * 1 #채운다
        #print(time, target)
        time_height.append((time, target))

final = []

min_time = time_height[0][0]

for time,height in time_height:
    if(time < min_time):
        min_time = time

for time,height in time_height:
    if(time == min_time):
        final.append((time, height))
        
max_final = max(final)
print(max_final[0], max_final[1])

deepred 2년 전 0

O(N^3) 시간복잡도로 보이는데

O(N^2) 로도 충분히 구현 가능합니다

로직을 다시 생각해보시면 좋을 것 같습니다

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

문제

문제

출처

ICPC

파이썬 시간초과

pgh268400 2년 전 0

deepred 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말