[백준 16922번] 로마 숫자 만들기 - Python

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

16922번: 로마 숫자 만들기

import sys

input=sys.stdin.readline
n=int(input())
result=[0]*(50*20+1) #50이 20번 쓰여 더해진게 최대값이므로
RomaNum=[1,5,10,50]
buf=[]
cnt=0

def recur(x,start):
    if x==n:
        result[sum(buf)]=1
        return
    for i in range(start,4):
        buf.append(RomaNum[i])
        recur(x+1,i)
        buf.pop()

recur(0,0)
print(sum(result))

전형적인 백트래킹 문제이다.

처음 문제 풀이를 할 때는 재귀함수 내의 반복문 시작점을 0으로만 하여 시작했어서 시간초과가 발생했었다.

중복조합의 원리를 적용하지 않고 중복순열의 원리를 적용하려고 하니 O(n!)대신 O(n^n)의 시간 복잡도가 적용되어

발생한 문제였다.

반복문의 시작점을 이전 방문한 노드보다 크거나 같도록 start 지점을 중복조합으로 적용시켜주니 해결되었다.