백준 16922번 로마 숫자 만들기

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

16922번: 로마 숫자 만들기

 

 

 

 

 

<접근방법>

전형적인 백트래킹 문제입니다.

조합을 만든 후 숫자 중복 체크를 해주면 됩니다.

 

 

<느낀 점>

처음에 순열로 짜서 틀렸다..

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int res;
int cal[4] = {1, 5, 10, 50};
bool visit[1001];

void dfs(int dep, int start, int num) {
	if (dep == n) {
		if (!visit[num]) {
			res++;
			visit[num] = true;
		}
		return;
	}

	for (int i = start; i < 4; i++) {
		num += cal[i];
		dfs(dep + 1, i, num);
		num -= cal[i];
	}

}

int main() {
	cin >> n;

	dfs(0, 0, 0);

	cout << res << '\n';

}