글 읽기 - 시간초과(파이썬)

wbjkwjj 3년 전 0

동적계획법을 이용해서

n=4부터 차례대로 최단경로를 저장해나가는 식으로 프로그래밍했습니다.

그렇지만 시간초과가 떴네요

더 개선할 점이 있다면 지적부탁드립니다

from sys import stdin
import copy
time=[0,0,1,1]#times taken to reach 1
way=[[],[],[1],[1]]#way to reach 1
n=int(stdin.readline())
for i in range(4,n+1):
    time.append(time[i-1]+1)
    if i%2==0:
        time[i]=min(time[i//2]+1,time[i])
    if i%3==0:
        time[i]=min(time[i//3]+1,time[i])
    add=0
    if i%6==0:
        s=min(time[i-1],time[i//2],time[i//3])
        if s==time[i//3]:
            add=(i//3)
        elif s==time[i//2]:
            add=(i//2)
        else:
            add=(i-1)
    else:
        if i%2==0:#i%3!=0
            if time[i//2]<time[i-1]:
                add=i//2
            else:
                add=i-1
        elif i%3==0:
            if time[i//3]<time[i-1]:
                add=i//3
            else:
                add=i-1
        else:
            add=(i-1)
    addlist=copy.deepcopy(way[add])
    addlist.append(add)
    way.append(addlist)
            
print(time[n])
print(n,end=' ')
for i in range(time[n]-1,-1,-1):
    print(way[n][i],end=' ')
print()

djm03178 3년 전 0

다음 수를 구할 때마다 전체 경로를 가져와서 복사하면 경로가 길어질수록 효율이 떨어집니다. 단순히 다음 수만을 저장해두면 반복적으로 그 수를 따라가는 것만으로 경로를 출력할 수 있습니다.

wbjkwjj 3년 전 0

왜 그 방법을 생각하지 못했을까요..!

감사합니다ㅠㅠ 좋은 하루 보내세요!

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

문제

문제

출처

ICPC

시간초과(파이썬)

wbjkwjj 3년 전 0

djm03178 3년 전 0

wbjkwjj 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말