2608 로마 숫자

 

쌩 노가다 문제였다. . .

 

int     to_num(string str)
{
    int sum = 0;

    str += " ";
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == 'I')
        {
            if (str[i + 1] == 'V')
            {
                sum += 4;
                i++;
                continue;
            }
            else if (str[i + 1] == 'X')
            {
                sum += 9;
                i++;
                continue;
            }
        }
        else if (str[i] == 'X')
        {
            if (str[i + 1] == 'L')
            {
                sum += 40;
                i++;
                continue;
            }
            else if (str[i + 1] == 'C')
            {
                sum += 90;
                i++;
                continue;
            }
        }
        else if (str[i] == 'C')
        {
            if (str[i + 1] == 'D')
            {
                sum += 400;
                i++;
                continue;
            }
            else if (str[i + 1] == 'M')
            {
                sum += 900;
                i++;
                continue;
            }
        }

        if (str[i] == 'I')
            sum += 1;
        else if (str[i] == 'V')
            sum += 5;
        else if (str[i] == 'X')
            sum += 10;
        else if (str[i] == 'L')
            sum += 50;
        else if (str[i] == 'C')
            sum += 100;
        else if (str[i] == 'D')
            sum += 500;
        else if (str[i] == 'M')
            sum += 1000;
    }

    return sum;
}

 

로마 숫자를 구하는 부분은 더럽지만 그래도 짤 수 있겠다 싶었다.

 

문제는 숫자를 로마 숫자로 변환하는 부분이었다... 너무 예외가 많아서 구현하는 데 시간이 오래 걸린다.

 

문자를 최소로 써야 하니 그리디로 해볼까?? 생각이 들었는데 아래와 같이 코드가 나와서 패스했다.

 

이렇게 코드를 짜니 컴공 4년 인생이 회의감이 든다.. 꼭 이렇게 해야할까...

 

이런 관계로 시간이 너무 오래 걸리는 문제였고 결국 이 부분은 다른 사람 코드 참고해서 넘기기로 했다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int i_num;
int x_num;
int c_num;
int m_num;

int v_num;
int l_num;
int d_num;

int iv_num;
int xl_num;
int cd_num;

int ix_num;
int xc_num;
int cm_num;

int dp[4005];

void    set_zero()
{
    l_num = 0;
    x_num = 0;
    c_num = 0;
    m_num = 0;
}

bool    check_i(int i)
{
    if (i < 1 || i_num == 3)
        return false;

    return true;
}

bool    check_v(int i)
{
    if (i < 5 || v_num > 0)
        return false;

    return true;
}

bool    check_x(int i)
{
    if (i < 10 || x_num == 3)
        return false;

    return true;
}

bool    check_l(int i)
{
    if (i < 50 || l_num > 0)
        return false;

    return true;
}

bool    check_c(int i)
{
    if (i < 100 || c_num == 3)
        return false;

    return true;
}

bool    check_d(int i)
{
    if (i < 500 || d_num > 0)
        return false;

    return true;
}

bool    check_m(int i)
{
    if (i < 1000 || m_num == 3)
        return false;

    return true;
}

bool    check_iv(int i)
{
    if (i < 4 || iv_num > 0)
        return false;

    return true;
}

bool    check_ix(int i)
{
    if (i < 9 || ix_num > 0)
        return false;

    return true;
}

bool    check_xl(int i)
{
    if (i < 40 || xl_num > 0)
        return false;

    return true;
}

bool    check_xc(int i)
{
    if (i < 90|| xc_num > 0)
        return false;

    return true;
}

bool    check_cd(int i)
{
    if (i < 400 || cd_num > 0)
        return false;

    return true;
}

bool    check_cm(int i)
{
    if (i < 900 || cm_num > 0)
        return false;

    return true;
}

int     to_num(string str)
{
    int sum = 0;

    str += " ";
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == 'I')
        {
            if (str[i + 1] == 'V')
            {
                sum += 4;
                i++;
                continue;
            }
            else if (str[i + 1] == 'X')
            {
                sum += 9;
                i++;
                continue;
            }
        }
        else if (str[i] == 'X')
        {
            if (str[i + 1] == 'L')
            {
                sum += 40;
                i++;
                continue;
            }
            else if (str[i + 1] == 'C')
            {
                sum += 90;
                i++;
                continue;
            }
        }
        else if (str[i] == 'C')
        {
            if (str[i + 1] == 'D')
            {
                sum += 400;
                i++;
                continue;
            }
            else if (str[i + 1] == 'M')
            {
                sum += 900;
                i++;
                continue;
            }
        }

        if (str[i] == 'I')
            sum += 1;
        else if (str[i] == 'V')
            sum += 5;
        else if (str[i] == 'X')
            sum += 10;
        else if (str[i] == 'L')
            sum += 50;
        else if (str[i] == 'C')
            sum += 100;
        else if (str[i] == 'D')
            sum += 500;
        else if (str[i] == 'M')
            sum += 1000;
    }

    return sum;
}

int     main()
{
    string s1, s2;
    cin >> s1 >> s2;

    int sum = to_num(s1) + to_num(s2);
    printf("%d\n", sum);

    for (int i = 0; i < 4005; i++)
    {
        vector<int> num(13);

        if (check_i(i))
            num[0] = dp[i-1] + 1;
        if (check_v(i))
            num[1] = dp[i - 5] + 1;
        if (check_x(i))
            num[2] = dp[i - 10] + 1;
        if (check_l(i))
            num[3] = dp[i - 50] + 1;
        if (check_c(i))
            num[4] = dp[i - 100] + 1;
        if (check_d(i))
            num[5] = dp[i - 500] + 1;
        if (check_m(i))
            num[6] = dp[i - 1000] + 1;

        int min_idx = 0;
        for (int j = 0; j < num.size(); j++)
        {
            if (num[j] < num[min_idx])
                min_idx = j;
        }


    }

    return 0;
}

 

 

이까지 짜고 넘어가도록 하겠습니다

 

제출한 코드는 아래와 같다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int     to_num(string str)
{
    int sum = 0;

    str += " ";
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == 'I')
        {
            if (str[i + 1] == 'V')
            {
                sum += 4;
                i++;
                continue;
            }
            else if (str[i + 1] == 'X')
            {
                sum += 9;
                i++;
                continue;
            }
        }
        else if (str[i] == 'X')
        {
            if (str[i + 1] == 'L')
            {
                sum += 40;
                i++;
                continue;
            }
            else if (str[i + 1] == 'C')
            {
                sum += 90;
                i++;
                continue;
            }
        }
        else if (str[i] == 'C')
        {
            if (str[i + 1] == 'D')
            {
                sum += 400;
                i++;
                continue;
            }
            else if (str[i + 1] == 'M')
            {
                sum += 900;
                i++;
                continue;
            }
        }

        if (str[i] == 'I')
            sum += 1;
        else if (str[i] == 'V')
            sum += 5;
        else if (str[i] == 'X')
            sum += 10;
        else if (str[i] == 'L')
            sum += 50;
        else if (str[i] == 'C')
            sum += 100;
        else if (str[i] == 'D')
            sum += 500;
        else if (str[i] == 'M')
            sum += 1000;
    }

    return sum;
}

int     main()
{
    string s1, s2;
    cin >> s1 >> s2;

    int sum = to_num(s1) + to_num(s2);
    printf("%d\n", sum);

    while (sum > 0) 
    { 
        if (sum >= 1000) 
            cout << "M", sum -= 1000; 
        else if (sum >= 900) 
            cout << "CM", sum -= 900; 
        else if (sum >= 500) 
            cout << "D", sum -= 500; 
        else if (sum >= 400) 
            cout << "CD", sum -= 400; 
        else if (sum >= 100) 
            cout << "C", sum -= 100; 
        else if (sum >= 90) 
            cout << "XC", sum -= 90; 
        else if (sum >= 50) 
            cout << "L", sum -= 50; 
        else if (sum >= 40) 
            cout << "XL", sum -= 40; 
        else if (sum >= 10) 
            cout << "X", sum -= 10; 
        else if (sum >= 9) 
            cout << "IX", sum -= 9; 
        else if (sum >= 5) 
            cout << "V", sum -= 5; 
        else if (sum >= 4) 
            cout << "IV", sum -= 4; 
        else 
            cout << "I", sum -= 1; 
    }


    return 0;
}

 

 

 

---

대박 개쩔어

 

이거 이렇게 하면 된다

 

막 III 연속 세 번 밖에 못 쓴다~ 이런 규칙때문에 쫄았는데 별거 아니었음ㅋㅋㅋㅋㅋ