[ 백준 16922 ] 로마 숫자 만들기 (C++)

백준의 로마숫자 만들기(16922) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 쉽게 이야기 하면 { 1, 5, 10 , 50 } 에서 N개를 뽑는 중복조합의 수를 출력하면 되는 문제이다.

   그렇다면 왜 조합인지 알아보자.

   로마에서는 숫자 I, V, X, L 4개를 사용한다고 하였는데, 이 때 이 숫자들이 의미하는 것이 { 1, 5, 10, 50 } 이라고 하였다.

   그렇다면 4개중에 2개를 뽑아보자.

   아마, II, IV, IX, IL, VI, VV, VX, VL, XI, XV, XX, XL, LI, LV, LX, LL 이렇게 나올 것이다.

   이 때 위에서 진자헥 표시된 2개의 숫자를 한번 봐보도록 하자. 저 2개의 숫자는 다른 숫자일까??

   뭐 실제 로마숫자에서는 다른 숫자일수도 있다. 그런데 이 문제에서는 각 숫자들의 합을 의미한다고 하였다.

   즉, I + X 나, X + I 나 똑같은 숫자라는 것이다. 이 말은 순서에 영향을 미치지 않는다는 말이다.

   { I, X } 를 뽑나 { X, I }를 뽑는 것이 같은 경우이기 때문이다.

   즉, 우리는 중복조합을 구현하게 되면, 이 문제의 답을 출력해낼 수 있는 것이다.

   아직 중복조합에 대해서 잘 알지 못한다면 아래의 글을 읽고 문제를 해결해 보도록 하자.

   [ 중복조합 구현하기 (Click) ]

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
using namespace std;
 
int N, Answer;
int Roma[] = { 1, 5, 10, 50 };
bool Visit[1000 + 1];
 
void Input()
{
    cin >> N;
}
 
void DFS(int Cnt, int D, int Total)
{
    if (Cnt == N)
    {
        if (Visit[Total] == false)
        {
            Visit[Total] = true;
            Answer++;
        }
        return;
    }
 
    for (int i = D; i < 4; i++)
    {
        DFS(Cnt + 1, i, Total + Roma[i]);
    }
}
 
 
void Solution()
{
    DFS(0, 0, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}