[백준] 16922번 로마 숫자 만들기 - 파이썬/백트래킹

https://www.acmicpc.net/problem/16922

import sys
sys.setrecursionlimit(10**6)

N = int(input())

nums = [1,5,10,50]

ans_list = []
sum_set = set()

def dfs(depth,N,idx):

    if depth == N:
        print(ans_list)
        sum_set.add(sum(ans_list))
        return

    for i in range(idx,4):
        ans_list.append(nums[i])
        dfs(depth+1,N,i)
        ans_list.pop()

dfs(0,N,0)

print(len(sum_set))

기본적인 백트래킹 문제 유형인데, 시간 초과가 발생하므로 반복 구간을 잘 설정해야 한다.