글 읽기 - 11727 파이썬 dp 질문 있습니다.

lggp 2년 전 0

제가 dp같은 이론은 잘 몰라서 이제 부터 연습하려고 이 문제에 도전했습니다.

제가 알기론 리스트에 예전에 계산해두었던 값들을 필요할 때 불러와서 계산 시간을 단축시키는 방식이 dp인데
아래 코드는 dp가 맞지 않나요? 그리고 어떻게 하면 시간초과 안 당할 수 있을 지 도움 부탁드립니다.

def Tile(n):
    if n==1:
        L[1]=1
        return 1
    if n==2:
        L[2]=2
        return 3
    if L[n]!=0:
        return L[n]
    else:
        return Tile(n-1)+2*Tile(n-2)

import sys
sys.setrecursionlimit(10**4)

N=int(input())
L=[0]*1001
print(Tile(N))

songmin9813 2년 전 0

dp를 재귀로 구현하신 것 같은데, 함수의 반복적인 호출 시 발생하는 context switching 시간도 고려해야 할 것 같습니다.

반복문으로 구현하면 연산 속도 및 메모리 낭비를 줄일 수 있습니다.

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

문제

문제

출처

ICPC

11727 파이썬 dp 질문 있습니다.

lggp 2년 전 0

songmin9813 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말