백준 16922 : 로마 숫자 만들기 (Python)

본문 링크

import sys
sys.setrecursionlimit(10**8)
N=int(input())
L=[1 , 5 , 10, 50]

visit=[False]*(10000)
total=0
Answer=0

def BackTracking(count , start, total):
    global Answer
    if count==N:
        if visit[total]==False:
            visit[total]=True
            Answer+=1
        return

    for i in range(start,4):
        BackTracking(count+1 , i , total+L[i])

BackTracking(0,0,0)
print(Answer)

📌 어떻게 접근할 것인가?

반복문이나 조합 라이브러리 써서 풀수도있지만 백트래킹 연습중이라 백트래킹으로 풀었습니다.

백트래킹보다는 사실 재귀에 가깝네요.

재귀함수를 통해서 매번 깊이를 1 씩 증가시키고 깊이가 $N$ 이라면 , 즉 문자열의 길이가 $N$ 이라면 그때 방문체크배열 visit 값에 따라서 Answer 을 증가시킵니다.

문제에서는 문자의 순서 상관없이 합만 생각하면 되므로 재귀에 들어갈때마다 현재값에다가 문자의 값을 계속 추가하는 방식으로 더해주었습니다.

또한 $N$ 은 20이하의 정수이기 때문에 visit 배열은 $10000$ 이상은 잡아주셔야 합니다.