[백준 16922] 로마 숫자 만들기 (C++)

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

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

int n, result;
int arr[4] = { 1, 5, 10, 50 };
bool check[1001];  //50 * 20 + 1

void func(int cnt, int index, int sum)
{
	if (cnt == n)
	{
		if (!check[sum])     // 1 + 5 = 5 + 1이기에 조건을 검
		{
			check[sum] = 1;  //방문처리
			result++;        //조건에 맞는 값 카운트 셈
		}
		return;
	}

	for (int i = index; i < 4; i++)
	{
		func(cnt + 1, i, sum + arr[i]);  //현재 인덱스 기준으로 자기 자신 + 뒤에 값들 더해감
	}                                    //ex) i = 1 (arr[1] = 5) -> 5, 10, 50 더해감
}

int main()
{
	cin >> n;
	func(0, 0, 0);  //초기 값은 0 0 0
	cout << result;
}

인덱스 값을 조절하여 재귀방식으로 구현했다.