글 읽기 - 재귀함수로 풀어보았는데, 시간 단축할 수 있는 방법 있을까요??

unhii 1년 전 0

재귀함수로 풀 수 있을 것 같았는데, 역시나 중복되는 부분을 많이 계산해서 그런지 시간초과가 뜨더라구요

memoization을 활용하려면 어떻게 코드를 작성해야 할까요??

도움 부탁드립니다 선생님들~~

N = int(input())


def zzang (n, k):
    if n ==0:
        return k
    if k == 1:
        return 1
    
    return zzang(n, k-1) + zzang(n-1, k)



for i in range(N):
    n = int(input())
    k = int(input())
    print(zzang(n, k))

dh0450 1년 전 0

하향식 DP를 위 코드에서 이용하려면 2차원 배열 ```dp[][]```을 만들어서

dp[n][k] = zzang(n, k-1) + zzang(n-1, k) 을 저장하고

if(dp[n][k] != 0) return dp[n][k] 를 재귀함수 앞에 넣는 방법으로 구현가능합니다.

unhii 1년 전 0

배움이 짧아서 무슨 말씀하시는지 정확히 이해를 못하겠습니다 ...ㅠㅠㅠ 자세한 설명 부탁드립니다 !!

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

문제

문제

출처

ICPC

재귀함수로 풀어보았는데, 시간 단축할 수 있는 방법 있을까요??

unhii 1년 전 0

dh0450 1년 전 0

unhii 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말