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

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

16922번: 로마 숫자 만들기

 

풀이 :

재귀적으로 구현해 주었는데 

 

현재 위치를 고르고 다음 위치를 가는 경우와

 

현재 위치를 고르고 또 현재 위치에 남아있는 경우

 

현재 위치를 고르지 않고 다음 위치를 가는 경우 이렇게 3가지로 분류해 주었다.

 

코드 ( C++ )

 

	#include <iostream>
	#include <vector>
	#include <set>
	using namespace std;
	int N;
	set<int> se;
	int num;
	int S[4] = { 1,5,10,50 };
	void solve(int begin, int cnt, int sum)
	{
	if (begin >= 4)
	return;
	if (cnt == N) {
	if (se.find(sum) == se.end()) {
	se.insert(sum);
	num++;
	}
	return;
	}
	int ret = 0;
	solve(begin + 1, cnt + 1, sum + S[begin]);
	solve(begin, cnt + 1, sum + S[begin]);
	solve(begin + 1, cnt, sum);
	}
	int main()
	{
	cin >> N;
	solve(0, 0, 0);
	cout << num << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub