글 읽기 - 왜 이 코드가 시간 초과가 나올까요?

knholic 6년 전 1

어느 부분이 문제여서 시간 초과가 나올까요...

def distance_calc(lst,y,dist=0):
    global res
    if len(lst) != 0:
        if lst[0][1] < y < lst[0][2]:
            distance_calc(lst[1:], lst[0][2], dist + abs(y-lst[0][2]))
            distance_calc(lst[1:], lst[0][1], dist + abs(y-lst[0][1]))
        else:
            distance_calc(lst[1:], y, dist)
    else:
        res.setdefault(dist,[])
        res[dist].append(y)

n = int(input())
start_y, max_x = map(int,input().split())
obstacle = []
for i in range(n):
    obstacle.append(list(map(int,input().split()))) 
obstacle = sorted(obstacle)
res = {}

distance_calc(obstacle, start_y)
key = sorted(res)[0]
dist = key + max_x
position = list(map(str,sorted(list(set(res[key])))))

print(dist)
print(len(position),' '.join(position))

knholic 6년 전 0

고수님들 도움좀 주세요. ㅜㅜ

jh05013 6년 전 0

input -> sys.stdin.readline

그리고 lst[1:]은 매우, 매우 비효율적입니다.

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

문제

문제

출처

ICPC

왜 이 코드가 시간 초과가 나올까요?

knholic 6년 전 1

knholic 6년 전 0

jh05013 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말