백준 16922 로마 숫자 만들기

n = int(input())
ans = set()
m = [1, 5, 10, 50]
def go(l):
    if len(l) == n:
        ans.add(sum(l))        
        return
    for i in m:
        go(l + [i])

go([])
print(len(ans))

시간초과 : 단순 재귀 중복되는 것들도 모두 찾음

n = int(input())
ans = set()
m = [1, 5, 10, 50]
def go(l):
    if len(l) == n:
        ans.add(sum(l))        
        return
    for i in range(len(m)):
        if l[-1] <= m[i]:
            go(l + [m[i]])

for i in range(4):
    go([m[i]])

print(len(ans))

중복을 없앤 재귀