백준 16922 로마 숫자 만들기(c++)

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

16922번: 로마 숫자 만들기

비교적 간단한 브루트포스 문제였습니다. 우선적으로 I,V,X,L을 사용하여 만들 수 있는 로마 숫자의 개수를 반환해야 합니다. 그런데 for문을 4번 돌리게 된다면, 시간 복잡도가 O(n^4)이 되기 때문에 다른 방안을 생각해야 합니다. 

I+V+X+L = n(사용할 로마 숫자 개수)이 되어야 합니다.

그러면 가장 큰 수를 나타내는 L의 개수는 n-X-V-I가 됩니다.

 나머지 부분은 가장 작은 수 I부터 n까지 탐색하고, V는 n-I까지, X는 n-I-V까지 탐색해서 만들 수 있는 로마 숫자의 개수를 리턴해주면 됩니다. check변수는 중복된 수는 의미가 없기 때문에 값을 만든다면, 즉시 check변수를 true를 걸어주었습니다.

 

<코드>

#include <iostream>

using namespace std;

bool check[1001]; // 만들 수 있는 로마 숫자 최대값 1000
int main() 
{
    int n;
    cin>>n;
    for(int i=0;i<=n;i++) {
        for(int v=0;v<=n-i;v++) {
            for(int x=0;x<=n-i-v;x++) {
                int l = n-i-v-x;
                int sum = i+5*v+10*x+50*l;
                check[sum] = true;
            }
        }
    }

    int ans = 0;
    for(int i=1;i<=1000;i++) {
        if(check[i]) ans +=1;
    }
    cout<<ans;
}