글 읽기 - Python3 제가 생각한 것이 맞는 지 봐주실 수 있나요?

parkjaeshik 4년 전 0

재귀함수를 통해 구현했는데요

코드 func 함수 중간에 주석 넣은 부분

#if arr[n]:
# return arr[n]

이거 안 쓰면 시간 초과 나더라구요.

이게 재귀호출할 때 이미 계산된 값 다시 계산 안 하고 바로 return 시키려고 넣은건가요?

파이참에선 빼든 안 빼든 num이 작을 때 값은 나오는데 숫자가 커지면 시간이 오래걸리나보네요.

import sys

num = int(sys.stdin.readline())
sys.setrecursionlimit(10**6)

arr = [0]*(num+1)
def func(n):
    if n==1:
        return 1
    if n==2:
        return 2
    #if arr[n]: 
    #    return arr[n]
    else:
        arr[n] = func(n-2)+func(n-1)
        return arr[n]

print(func(num)%10007)

shg9411 4년 전 1

메모이제이션이라고 하죠.

이미 구했던 값을 다시 구하지 않기 위해서 사용합니다.

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

문제

문제

출처

ICPC

Python3 제가 생각한 것이 맞는 지 봐주실 수 있나요?

parkjaeshik 4년 전 0

shg9411 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말