[BOJ 16922 // C++] 로마 숫자 만들기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16922번 문제인 로마 숫자 만들기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/16922

16922번: 로마 숫자 만들기

이 문제에서는 정확히 총 N개의 I, V, X, L을 이용하여 각 로마숫자가 나타내는 수의 총합의 가짓수를 구하는 문제이다.

N개의 문자를 전부 이용해야 하고, N의 범위가 20까지이므로, 백트래킹을 이용해 전체를 탐색해도 충분히 풀 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin; using std::cout;

bool chk[1001];
int cnt = 0;

void L(int N, int sum) {
    if (!chk[sum + 50 * N]) {
        chk[sum + 50 * N] = 1;
        cnt++;
    }
}

void X(int N, int sum) {
    for (int i = 0;i <= N;i++) {
        L(N - i, sum + 10 * i);
    }
}

void V(int N, int sum) {
    for (int i = 0;i <= N;i++) {
        X(N - i, sum + 5 * i);
    }
}

void I(int N) {
    for (int i = 0;i <= N;i++) {
        V(N - i, i);
    }
}

int main()
{
    int N; cin >> N; I(N); cout << cnt; return 0;
}