[백준] 16922번 로마 숫자 만들기 - Python / 알고리즘 중급 2/3 - 브루트 포스 - 문제

---

---

---

💡 문제

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

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

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

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

입력

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

출력

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

---

💭 접근

간단하게 DFS를 사용하여 1, 5, 10, 50 숫자들을 조합하여 나올 수 있는 숫자들을 ans 리스트에 기록하고, 그 개수를 출력하면 되는 문제.

---

📒 코드

def dfs(depth, start):
    global idx

    if depth == n:
        ans[idx] = 1
        return
    
    for i in range(start, 4):
        idx += num[i]
        dfs(depth + 1, i)
        idx -= num[i]

n = int(input())
num = [1, 5, 10, 50]
ans = [0 for _ in range(1001)] # 최대 50 x 20 = 1000
idx = 0

dfs(0, 0)

print(sum(ans))

---

💭 후기

간단한 조합 문제였다.

---

🔗 문제 출처

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

---