백준 알고리즘 16922번 로마 숫자 만들기(python)

수학 & 백트래킹 문제이다. 그런데 백트래킹을 써서 푸니까 시간 초과가 나온다.

시간 초과가 뜰 만 한 코드이긴 한데 어떻게 해결해야 할지 모르겠어서 일단 반복문을 사용해서 해결했다.

반복문 풀이(통과)

N = int(input())
s = set()
for i in range(N+1):
    for j in range(N+1 - i):
        for k in range(N+1 - i - j):
            t = N-i-j-k
            n = i + 5*j + 10*k  + 50*t
            s.add(n)

print(len(s))

백트래킹 풀이(시간 초과)

def dfs(depth, s):
    if depth == N:
        check[s] = 1
        return ;
    for i in range(4):
        dfs(depth+1, s+nums[i])
        
N = int(input())
nums = [1, 5, 10, 50]
check = [0]*(50*20+1)
dfs(0, 0)
cnt = 0
for i in check:
    if i:
        cnt += 1
print(cnt)