For a number written in Roman numerals to be considered valid there are basic rules which must be followed. Even though the rules allow some numbers to be expressed in more than one way there is always a "best" way of writing a particular number.
For example, it would appear that there are at least six ways of writing the number sixteen:
IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI
However, according to the rules only XIIIIII and XVI are valid, and the last example is considered to be the most efficient, as it uses the least number of numerals.
The 11K text file, roman.txt (right click and 'Save Link/Target As...'), contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; see About... Roman Numerals for the definitive rules for this problem.
Find the number of characters saved by writing each of these in their minimal form.
Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.
로마 숫자로 쓰인 숫자는 기초 규칙만 지키면 유효하다고 고려된다. 아래 규칙은 어떤 숫자는 한 가지 이상 방법으로 표현될 수 있지만, 특정 숫자를 나타나는 "가장 좋은" 방법은 늘 존재한다.
예를 들어, 16을 표현하는 데 다음과 같이, 적어도 6가지 방법은 있다.
IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI
그러나, 규칙에 의해 XIIIIII와 XVI만 유효하고, XVI가 가장 적은 숫자를 사용하므로 가장 효율적인 것으로 고려된다.
11K 텍스트 파일 roman.txt (우클릭하고 "다른 이름으로 링크 저장")에는 1천개의 유효한 로마 숫자가 있지만, 가장 적은 숫자는 아니다; 구체적인 규칙을 위해서는 About... Roman Numerals 를 참조하라.
최소화 된 형태 바꾸었을때 줄어든 글자의 갯수를 구하시오.
주의: 파일에 있는 로마 숫자는 4개 이상 연속된 숫자가 없다고 가정할 수 있다.
--------------------------------------------------------------------------
자주 보면서도 몰랐던 로마 숫자인데 그것을 응용하는 문제가 나왔다. 참조를 보면 I=1, V=5, X=10, L=50, C=100, D=500, M=1000이며, ①큰 수에서 작은 수로 쓰여지고, ②M, C, X는 동일한 작은 수로 표현되지 않으며, ③D, L, V는 한 번만 나오는 것이 규칙으로 되어 있다. 예시 설명에서, XIX(19)는 맞지만 IXX(9, 10)은 안되고(①위반) VVVIIII 안되며(③위반), XIIIIIIIII, XVIIII보다는 XIX를 선호(최소화)하는 것으로 되어 있으며, 4는 IIII보다는 IV, 9는 VIIII보다는 IX, 40은 XXXX보다는 XL, 90은 LXXXX보다는 XC, 400은 CCCC보다는 CD, 900은 DCCCC보다는 CM형태가 최소화되므로 선호하는 것으로 되어 있다.
문제에서는 roman.txt에 있는 로마 숫자를 최적화하고, 그 과정에서 몇 글자나 줄었는지 구하라고 요구하고 있는데, 영어가 짧은 덕에 2가지를 잘못 전제하고 시작했다. 모든 roman.txt의 숫자가 최적화되지 않은 상태에 있으므로, 최적화시킨 단어 갯수를 구하라고 이해했던 것이다.
모든 roman.txt 숫자가 최적화되지 않았다고 생각했기 때문에 단순하게 읽히는 로마 숫자를 아라비아 숫자로 단순변환시켜 로마숫자로 최적화고, 바뀐 단어수를 구했는데 오답이 나왔다. 아무래도 문제를 잘 못 이해해서 엉뚱하게 풀었던 것 같아서 찾아보니 위와 같은 답을 요구하고 있었다.
그 말은, 복잡하게 아라비아 숫자로 변환할 필요 없이 (문제 마지막에서 같은 문자가 4개 이상 없다고 전제했으므로) 900, 400, 90, 40, 9, 4에 해당하는 로마 숫자를 최적화시키고 그 과정에서 몇 글자나 줄어들었는지만 구하면 되는 문제였다. 수학 지식보다는 문자열 조작만 잘 하면 되는 것이어서 문제에서 제시한 난이도보다는 쉽게 해결 가능했다.