[BOJ] 로마 숫자 만들기 16922번 C++

 

 

문제

로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.

하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.

실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.

로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.

입력

첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.

 

접근 방식

 

간단한 문제이지만 잘못 풀면 시간초과가 발생하는 문제다

문제에서 문자의 순서는 상관없기 때문에

XI나 IX가 같은 값이다

따라서 둘 중 한번만 선택하면 되기 때문에

재귀 함수에 현재 선택한 인덱스값을 함께 매개변수로 전달해

중복 발생하는 값을 최소로 줄일 수 있다

 

코드

 

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

int N;
set<int> s;
int n[4] = {1,5,10,50};

void sol(int cnt, int i, int total) {
    ios::sync_with_stdio(false); cin.tie(0);

    if(cnt == N) {
        s.insert(total);
        return;
    }
    for(int x = i; x<4; x++) {
        sol(cnt+1, x, total + n[x]);
    }
}

int main() {
    cin >> N;
    sol(0,0, 0);
    cout << s.size();
}