[C++] 백준 문제풀이 (Bruteforcing) 16922번 로마 숫자 만들기

 

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

16922번: 로마 숫자 만들기

 

 

//[C++] 백준 문제풀이 (Bruteforcing)
#include <bits/stdc++.h>


int n;
int values[4] = {1, 5, 10, 50};
bool check[1001];
int ret = 0;


void dfs(int depth, int select, int sum){
    if (depth == n){
        if (check[sum] == false){
            check[sum] = true;
            ++ret;
        }
        return;
    }

    for (int i = select; i < 4; ++i){
        dfs(depth + 1, i, sum + values[i]);
    }
}


int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n;
    dfs(0, 0, 0);

    std::cout << ret << "\n";
    return 0;
}