class Solution {
public:
	string intToRoman(int num) {
		vector<string> roman {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
		vector<int> integers {1000, 900, 500, 400,  100, 90,   50,   40,  10,  9,    5,   4,     1 };
		string r;
		int times = 0;

		for (int i = 0; i < integers.size(); ++i) {
			if (num >= integers[i]) {
				times = num / integers[i];
				num -= times * integers[i];
				for (int j = times; j > 0; --j) {
					r.append(roman[i]);
				}
			}
		}
		return r;
	}
};