백준 16922번 로마숫자 만들기

문제

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

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

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

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

입력

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

출력

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

 

 

 

같은 수 여러번 나올 수 있지만 순서의 상관이 없으므로, 0100 이 나왔으면 1000이 안나오길 바람.

따라서 idx 부터 다시 시작으로 재구성.

1로 시작하면 그 이후 0이 안나오면 됨.

0이 있는 상태에서 1이 포함될 수 있는 모든 케이스는 이미 0에서 다 구해졌으므로..

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>
#include<map>
using namespace std;

bool check[1001];
int arr[4] = { 1,5,10,50 };
int N;
int cost, res;
void DFS(int idx, int cur)
{
	if (cur == N)
	{
		if (!check[cost])
		{
			check[cost] = true;
			res++;
		}
		return;
	}

	for (int i = idx; i < 4; i++)
	{
		cost += arr[i];
		DFS(i, cur + 1);
		cost -= arr[i];
	}
}
int main(void)
{


	cin >> N;
	for (int i = 0; i < 4; i++)
	{
		cost += arr[i];
		DFS(i,1);
		cost -= arr[i];
	}
	cout << res << endl;
}