글 읽기 - 파이썬 딕셔너리와 2차원 리스트의 메모이제이션 결과가 다른데 왜일까요?

abc3242 5년 전 0

메모이제이션을 딕셔너리에 했다가 메모리 초과가 떠서 2차원 리스트로 바꾸었습니다.

그런데 예제의 실행 결과가 서로 다릅니다.

같은 점화식을 적용했는데 결과가 왜 이럴까요?

# 딕셔너리 이용한 코드 
# 예제 입력하면 10 출력

from sys import setrecursionlimit
setrecursionlimit(10**7)

cache = dict()
def solve(k, i):
    if k <= 0:
        print(int(k==0), end = " ")
        return int(k == 0)

    if i >= len(coins):
        return 0
    
    if (k, i) in cache:
        return cache[(k,i)]

    ret = 0

    while k >= 0:
        ret += solve(k,i+1)
        k -= coins[i]
    
    cache[(k, i)] = ret
    return ret

    
n, k = map(int, input().split())
coins = tuple(int(input()) for i in range(n))

print(solve(k,0))

# 2차원 리스트 이용한 코드 
# 예제 입력시 15 출력 

from sys import setrecursionlimit
setrecursionlimit(10**7)

def solve(money, i):
    
    if money <= 0:
        return int(money == 0)
    if i >= N:
        return 0
    if cache[money][i] != -1:
        return cache[money][i]

    ret = 0

    while money >= 0:
        ret += solve(money,i+1)
        money -= coins[i]
    
    cache[money][i] = ret
    return ret
    
N, K = map(int, input().split())
cache = [ [-1]*N for _ in range(K+1) ]
coins = tuple(int(input()) for i in range(N))

print(solve(K,0))

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

문제

문제

출처

ICPC

파이썬 딕셔너리와 2차원 리스트의 메모이제이션 결과가 다른데 왜일까요?

abc3242 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말