boj 16922 로마 숫자 만들기

www.acmicpc.net/problem/16922

16922번: 로마 숫자 만들기

1, 5, 10, 50을 배열에 넣어놓고 조합으로 해결하였습니다.

인덱스와 갯수와 합을 유지시키면서 재귀를 돌려줍니다.

N개를 뽑으면 숫자를 저장하였는데 이 때 중복된 값을 넣으면 안되므로 set에 넣어줍니다.

함수가 끝나고 최종 set의 크기를 출력하시면 됩니다.

 

 

#include <iostream>
#include <set>
using namespace std;
 
set<int> s;
int list[4];
int N;
 
void init() {
    list[0] = 1;
    list[1] = 5;
    list[2] = 10;
    list[3] = 50;
}
 
void func(int idx, int cnt, int sum) {
    if (cnt == N) {
        if (sum > 0) s.insert(sum);
        return;
    }
 
    for (int i = idx; i < 4; i++) {
        func(i, cnt + 1, sum + list[i]);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> N;
    init();
    func(0, 0, 0);
    cout << s.size() << '\n';
 
    return 0;
}