[Baekjoon/C++] 16922번 - 로마 숫자 만들기

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

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

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

 

입력

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

 

출력

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

 

---

풀이

#include <iostream>
using namespace std;

int N, cnt = 0;
bool check[1001];

void dfs(int dth, int now, int sum);

void dfs(int dth, int now, int sum) {
    if (dth == N) {
        if (!check[sum]) {
            check[sum] = true;
            cnt++;
        }

        return;
    }

    int arr[4] = { 1, 5, 10, 50 };

    for (int i = now; i < 4; i++)
        dfs(dth + 1, i, sum + arr[i]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    dfs(0, 0, 0);

    cout << cnt << '\n';

    return 0;
}

dfs로 문제를 풀었다. 문제에 따르면 IX나 XI나 같은 숫자이기에 IX를 탐색했는데, XI도 탐색하는 것은 불필요한 행위이다. 그렇기에 now 매개변수를 통해 위와 같은 상황이 일어나지 않도록 하였다.