// 演算法：把 13 個「值 → 羅馬符號」候選由大到小排好，貪心地把最大可用值扣掉並接上符號。
// Algorithm: identical greedy strategy — walk a largest-first table of 13 (value, symbol)
// pairs, repeatedly subtracting the biggest value that fits while appending its symbol.

#include <string>   // std::string / C++ 的字串類別 / C++'s string class
#include <vector>   // std::vector / 動態陣列 / dynamic array container

class Solution {
public:
    std::string intToRoman(int num) {
        // const 表示這張表不會被修改 / const means we promise not to mutate the table.
        // std::vector<std::pair<int,std::string>>：每個元素是「整數值 + 對應符號」一組。
        // Each element pairs an int value with its Roman string; pair = two-element bundle.
        const std::vector<std::pair<int, std::string>> table = {
            {1000, "M"},  {900, "CM"}, {500, "D"},  {400, "CD"},
            {100,  "C"},  {90,  "XC"}, {50,  "L"},  {40,  "XL"},
            {10,   "X"},  {9,   "IX"}, {5,   "V"},  {4,   "IV"},
            {1,    "I"}
        };

        std::string result;       // 空字串開始，逐步拼接 / Start empty, append as we go.
        result.reserve(16);       // 預先配置最壞情況容量，避免多次重新配置 / Pre-allocate
                                  // capacity for the worst case (~15 chars) to avoid reallocs.

        // range-for + structured binding：直接把 pair 拆成 value 和 symbol 兩個變數。
        // C++17 structured binding: `auto& [a, b] = pair` unpacks the pair into two names.
        // 用 const auto& 避免複製 string / `const auto&` avoids copying the string each iter.
        for (const auto& [value, symbol] : table) {
            // 當前候選值還能扣就一直扣 / Keep subtracting this value while it still fits.
            while (num >= value) {
                result += symbol;  // string 的 += 直接把右邊接到尾端 / += appends in place.
                num -= value;      // 推進 num，保證迴圈會結束 / Decrease num to make progress.
            }
        }

        return result;  // RVO 會省略複製，回傳成本接近零 / Return value optimization avoids
                        // an extra copy here.
    }
};