[백준 16922] 로마 숫자 만들기 - 파이썬

문제

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

16922번: 로마 숫자 만들기

 

 

풀이 방법

로마숫자를 더해서 나오는 수에 해당하는 인덱스 (예를 들어 로마숫자 IX → 11) 에 1을 더해준다. 

나중에 로마숫자로 만들 수 있는 숫자의 총 개수를 sum 함수로 쉽게 세기 위함이다.

 

재귀함수를 사용해서 숫자를 반복적으로 더해준다. 

 

 

코드

n = int(input())
roma = [1, 5, 10, 50]
arr = [0] * 1001
num = 0


def dfs(cur, start):
    global num
    if cur == n:
        arr[num] = 1
        return
    
    for i in range(start, 4):
        num += roma[i]
        dfs(cur+1, i)
        num -= roma[i]



dfs(0, 0)
print(sum(arr))