글 읽기 - 13303 파이썬 시간초과

jnha12345 1년 전 0

딕셔너리에다가

같은 y에서 더 짧은 거리만을 저장하기 위해 y값을 key로 저장하고, 그떄의 이동 거리를 value로 저장하면서 min값을 저장하는 방식으로 코드를 짰습니다. 그리고 계속해서 del을 해주어 필요없는 계산을 없애는 과정을 추가해 시간초과를 막아보려 했지만, 결국 n이 100000 가까이 갔을때는 시간초과가 나는데 어떤방식으로 바꿔야할지 궁금합니다..

솔직히 인터넷에 python 풀이도 없는 상황에서 힌트가 절실히 필요합니다..

도움주시면 정말 감사하겠습니다

import sys
input = sys.stdin.readline

INF = int(1e9)
n = int(input())
sy, mx = map(int, input().split()) # y, max x value
nlist = []
for _ in range(n) :
    nlist.append(list(map(int, input().split())))
nlist.sort(key=lambda x: x[0])
s = {}
s[sy] = 0
idx = 0
while idx < n :
    keys = list(s.keys())
    for y in keys :
        d = s[y]
        if nlist[idx][1]<y<nlist[idx][2] :
            s.setdefault(nlist[idx][1], INF)
            s.setdefault(nlist[idx][2], INF)
            s[nlist[idx][1]] = min(s[nlist[idx][1]], d+y-nlist[idx][1])
            s[nlist[idx][2]] = min(s[nlist[idx][2]], d+nlist[idx][2]-y)
            del s[y]
    idx += 1
    print(s)
cnt = INF
ans = [k for k, v in s.items() if min(s.values()) == v]
print(s[ans[0]]+mx)
ans.sort()
print(len(ans), *ans)

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

문제

문제

출처

ICPC

13303 파이썬 시간초과

jnha12345 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말