백준 16922번 : 로마 숫자 만들기

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

16922번: 로마 숫자 만들기

 문제설명 

 

1. 사용 할 수있는 로마숫자가의 갯수 N이 주어지고  ,N개의 로마숫자를 이용하여 만들 수 있는 서로다른 수의 갯수를      출력.

 

 알고리즘 

 

1.중복 조합을 이용하여 구하는데, 똑같은 숫자가 여러개 만들어질경우 한개로 생각하기때문에 숫자가 겹치는지 여부를    배열로 체크해주면 된다.

 

 코드 

 

#include<iostream>
 
using namespace std;
 
bool arr[10000];
int n, num[4] = { 1,5,10,50 };
int result = 0;
void func(int cnt,int number,int idx) {
    
 
    //cnt=n 일때 이미 숫자를 만든적이있으면 return 
    //없으면 result++
    if (cnt == n) {
        if (arr[number])return;
        arr[number] = 1;
        result++;
        return;
    }
 
    
    for (int i = idx; i < 4; i++) {
        func(cnt + 1, number + num[i],i);
    }
 
 
}
 
int main() {
 
    cin.tie(NULL);
    ios::sync_with_stdio(0);
 
 
    cin >> n;
    func(0, 0,0);
    cout << result;
 
}