글 읽기 - python 1%에서 시간 초과

manen0122 1년 전 0

안녕하세요,

python을 사용하여 구현했고, 1%에서 시간초과되는 결과를 가져왔습니다.

pypy를 사용하여서도 제출했는데 같은 결과입니다.

for loop를 더 줄이고 싶었는데 500*500 이하로 줄일 수 없을 것 같아서 진행했습니다.

개인적으론 이중 구문 안의 line 15 - line 21 사이의 구문을 줄여야할 것같은데 감이 잡히지 않습니다.

import sys

N, M, B = map(int,input().split(" ")) # N,M,B 값 할당

all = []
min_time = 1000000000000

for i in range(N) :
    all = all + sys.stdin.readline().split(" ")
all = list(map(int, all))               #전체 값 입력 및 자료형 변환

for h in set(all) :  # 높이 값들 중 하나인 h (이 h가 적절한 땅의 높이인지 판단할 것, 대상 높이) 에 대해서
    suma = B
    time = 0
    for elem in all :   # 전체 값 중 하나인 elem (h와의 차이를 구해서 값을 time에 저장할 것) 에 대해서
        t = elem - h
        if t > 0 :   
            time += t*2      # elem 이 h보다 크면, 쌓는 것이므로 2초
        elif t < 0 :
            time -= t        # elem 이 h보다 작으면 제거하는 것이므로 1초
        suma += t            # elem - h는 블록의 필요한 갯수 혹은 가진 갯수이므로, B + (차의 총합) 의 부호가 블록의 여유분이 있는지 아닌지 결정
    if suma < 0 :
        continue
    if min_time >= time :   # 계산 된 time이 최소값인지 확인 후 저장
        min_time = time
        block = h
print(min_time,block)

djm03178 1년 전 1

PyPy3로 몇 번 제출해보았는데 시간 초과는 안 나고 틀렸습니다만 받았습니다.

djm03178 1년 전 1

시간을 크게 개선시킬 수 있는 부분이라면 9번째 줄을 all = all + ... 대신에 all += 으로 쓰는 것입니다. 전자는 기존의 리스트를 복사하여 새로운 리스트를 만들고 그 뒤에 새로운 내용을 덧붙이기 때문에 총 시간 복잡도가 O(N^2M)이 되지만, 후자는 기존의 리스트의 뒤에 새로운 내용만 덧붙이기 때문에 O(NM)이 됩니다.

manen0122 1년 전 0

답변이 정말 늦었네요, 죄송합니다. 몇가지 사항을 수정했더니 간신히 해결되었습니다.

친구와 논의해보니 이 알고리즘을 아예 새로 다시 짜는 것이 건강에 이롭다고 결론내렸습니다.

행복한 하루 되세요!

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

문제

문제

출처

ICPC

python 1%에서 시간 초과

manen0122 1년 전 0

djm03178 1년 전 1

djm03178 1년 전 1

manen0122 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말