백준 16922 (로마 숫자 만들기)

 

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

16922번: 로마 숫자 만들기

해당 문제는 로마 숫자인 I, V, X, L 이 주어지며 각각의 문자는 1, 5, 10, 50과 대응한다. 이러한 로마 숫자를 n개 사용하여 만들 수 있는 모든 숫자의 개수를 출력하는 문제이다.

추가로 기존의 로마 숫자와는 다르게 순서에 상관 없이 대응하는 숫자를 더해주면 된다. 따라서 어떠한 문자가 어떤 순서로 오더라도 결국 도출되는 숫자는 같다 따라서 조합을 사용하여 문제를 풀이하면 된다.

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;
vector<char> numList = { 'I', 'V', 'X', 'L' };
int used[1001];
string resList;
int n, cnt;

int checkList(string str){
	int n = str.length();
	int sum = 0;

	for (int i = 0; i < n; ++i){

	}
	return sum;
}

void dfs(int level, int idx, int sum){
	if (level == n){
		if (used[sum] == 0) {
			used[sum] = 1;
			++cnt;
		}
		return;
	}

	for (int i = idx; i < 4; ++i){
		if (numList[i] == 'I') dfs(level + 1, i, sum + 1);
		else if (numList[i] == 'V') dfs(level + 1,i, sum + 5);
		else if (numList[i] == 'X') dfs(level + 1,i, sum + 10);
		else if (numList[i] == 'L') dfs(level + 1,i, sum + 50);
	}
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n;
	dfs(0, 0, 0);
	cout << cnt << endl;
}