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

16922번: 로마 숫자 만들기

 

문제

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

---

풀이

I, V, X, L 네 가지 문자를 N개 사용해 만들 수 있는 조합을 구하면 된다. 단, 각 문자가 의미하는 수가 있고 이 합이 중복되는 경우를 제거해야 한다. 이유는 IXI와 IIX를 같은 12로 보기 때문이다.

백트래킹으로 가능한 경우의 수를 모두 만들어보며 visited 배열을 사용해 이미 센 수인지 확인한다. 1, 5, 10, 50 순으로 조합해 보되 예를들어 4가지 문자를 조합하는 경우 1, 1, 1, 5와 1, 1, 5, 1은 같기 때문에 이미 3번째에 5를 고른 경우엔 4번째에 1을 고를 필요가 없어진다. 따라서 5부터만 확인한다.

---

코드

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, ans=0;
int visited[1001];
int rome[4]={1,5,10,50};

void dfs(int m, int depth, int sum) {
	if (depth == n) {
		if (!visited[sum]) {
			visited[sum]=1;
			ans++;
		}
		return;
	}
	for (int i = m; i < 4; i++)
		dfs(i, depth+1, sum+rome[i]);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	dfs(0,0,0);
	cout << ans;
}