글 읽기 - 파이썬 조언 부탁드립니다. ㅠㅠ

kyuha0731 2년 전 0

python으로 제출하면 시간초과가 뜨고, pypy로 제출하면 틀렸다고 뜨네요..

반례와 시간 줄이는 조언 부탁드립니다. ㅠㅠ

어떻게 풀어야 할지 고민하다가 제가 접근한 방법은,

건물들을 짓는 순서를 bps로 결정하고,

어떤 건물을 짓는 데 걸리는 최대 시간을 저장하여 dp로 총 시간을 계산했습니다.

제출하면 시간초과가 바로 떠 버리는데, 어디가 비효율적일까요? ㅠㅠ

다른 질문들을 찾아보니 재귀dp로 풀으신 분들이 많은 것 같은데,

제가 생각한 방법은 재귀dp보다 비효율적인 방법인가요?

from sys import stdin,stdout
r=stdin.readline

res=[]
for _ in range(int(r())):
    dic={}
    n,k=map(int,r().split())
    d=list(map(int,r().split()))
    for i in range(k):
        x,y=map(int,r().split())
        if x not in dic:dic[x]=[0]
        if y in dic:
            if dic[y]==[0]:dic[y]=[x]
            else:dic[y].append(x)
        else:dic[y]=[x]
    w=int(r())
    if w not in dic:dic[w]=[0]

    order=[w]
    def ordering(visited):
        if visited==[0]:return
        else:
            global order
            next=[]
            for i in visited:
                if not i:continue
                if i not in order:order.append(i)
                for j in dic[i]:
                    if j not in next:next.append(j)
            ordering(next)
    ordering(dic[w])
    order=order[::-1]
    # print(order)

    dp=[0]*(max(order)+1)
    for i in order:
        dp[i]=max([dp[_] for _ in dic[i]])+d[i-1]
    # print(dp)

    res.append(str(dp[w]))
    
stdout.write("\n".join(res))

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

문제

문제

출처

ICPC

파이썬 조언 부탁드립니다. ㅠㅠ

kyuha0731 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말