Problem 2.2.3 Preface Numbering

출처: https://train.usaco.org/usacogate

---

문제 설명

Given N (1 <= N < 3,500), the number of pages in the preface of a book, calculate and print the number of I's, V's, etc. (in order from lowest to highest) required to typeset all the page numbers (in Roman numerals) from 1 through N. 

Do not print letters that do not appear in the page numbers specified.

입력

A single line containing the integer N.

출력

The output lines specify, in ascending order of Roman numeral letters, the letter, a single space,
and the number of times that letter appears on preface page numbers. Stop printing letter totals
after printing the highest value letter used to form preface numbers in the specified set.

입력 예

5

출력 예

I 7
V 2

( I, II, III, IV, V) -> I: 1(1)+2(2)+3(3)+1(4) = 7, V : 1(4) + 1(5) = 2

---

문제 풀이

1 부터 입력받은 숫자까지 Roman 숫자로 표현할때 각 숫자들이 몇번 나오는지 세는 프로그램을 작성한다.

Roman 숫자표현에서 나오는 문자는 7가지 이다.( I - 1, V - 5, X - 10, L - 50, C - 100 , D - 500, M - 1000) 

이런 7개 문자들이 몇번 나오는지 unordered_map<char, int> 형태로 기록한다.

프로그램 내용

 

...
	string ones[9] = {"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    string tens[9] = {"X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    string hundreds[9] = {"C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    string thousands[3] = {"M", "MM", "MMM"};
...
    unordered_map<char, int> m;
    for (int i = 1; i <= N; i++) {
        int num = i;
        
        if (num / 1000 > 0) {
            count(m, thousands[num / 1000 - 1]);
            num %= 1000;
        }
        if (num / 100 > 0) {
            count(m, hundreds[num / 100 - 1]);
            num %= 100;
        }
        if (num / 10 > 0) {
            count(m, tens[num / 10 - 1]);
            num %= 10;
        }
        if (num > 0) {
            count(m, ones[num - 1]);
        }
    }
    if (m.find('I') != m.end()) fout << "I " << m['I'] << endl;
    if (m.find('V') != m.end()) fout << "V " << m['V'] << endl;
    if (m.find('X') != m.end()) fout << "X " << m['X'] << endl;
    if (m.find('L') != m.end()) fout << "L " << m['L'] << endl;
    if (m.find('C') != m.end()) fout << "C " << m['C'] << endl;
    if (m.find('D') != m.end()) fout << "D " << m['D'] << endl;
    if (m.find('M') != m.end()) fout << "M " << m['M'] << endl;
...

 

Chapter 2. Bigger Challenges ( link )