[백준] 16922번: 로마 숫자 만들기 (python)

16922번: 로마 숫자 만들기

---

문제 )

로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.

하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.

실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.

로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.

 

 

입력 :

첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.

 

 

출력 :

첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.

 

 

 

 

풀이)

처음에는 set을 이용한 중복제거를 이용하여 문제를 풀려고 했으나

시간 초과에 부딪혔다.

시간 초과가 일어난 이유는 cur == n에 도달하는 모든 경우에서 중복을 제거하기 때문이었다.따라서 이 문제에서는 for문의 출발점을 조정하면서 중복된 값이 나오지 않도록 하고,중복을 판별하는 arr를 만들어 만들 수 있는 숫자의 개수를 세어주었다.

 

def recur(cur, start):
    global num
    if cur == n:
        arr[num] = 1
        return
 
 
    for i in range(start, 4):
        num += li[i]
        recur(cur + 1, i)
        num -= li[i]
 
 
n = int(input())
li = [1, 5, 10, 50]
arr = [0] * (50 * 20 + 1)
num = 0
recur(0, 0)
print(sum(arr))

---

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

16922번: 로마 숫자 만들기