問題
ローマ数字では I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000 を使います。記号は大きいものから順に並べて足し合わせますが、例外として6つの減算表記があります。IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900 です。n を標準的な形に変換してください。標準形では、同じ記号を4つ並べる代わりに必ず減算表記を使います(4 は IV であり、IIII とは書きません)。
integer_to_roman(n) を実装してください。
入力
n:変換する数。
出力
ローマ数字を大文字の文字列で返してください。
制約
1 ≤ n ≤ 3999
例
例 1
入力:
n = 1994
期待される出力:
expected = "MCMXCIV"
入力:
long long n = 1994;
期待される出力:
std::string expected = "MCMXCIV";
入力:
long n = 1994;
期待される出力:
string expected = "MCMXCIV";
解説
1000 + 900 + 90 + 4 なので M、CM、XC、IV となり、"MCMXCIV" です。
例 2
入力:
n = 58
期待される出力:
expected = "LVIII"
入力:
long long n = 58;
期待される出力:
std::string expected = "LVIII";
入力:
long n = 58;
期待される出力:
string expected = "LVIII";
解説
50 + 5 + 3 なので L、V、III となり、"LVIII" です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
記号と6つの減算表記をまとめて、値の順に並べた表を作ります。
ヒント 2
残りの値に収まる最大の値を繰り返し取っていきます。
ヒント 3
4、9、3999 を手で試して、表が正しいか確かめましょう。
目安の計算量
時間 O(1)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。