책 이야기

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에 해당하는 로마 숫자를 최적화시키고 그 과정에서 몇 글자나 줄어들었는지만 구하면 되는 문제였다. 수학 지식보다는 문자열 조작만 잘 하면 되는 것이어서 문제에서 제시한 난이도보다는 쉽게 해결 가능했다.

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

1에서 5까지 숫자를 영어 단어로 적으면 one, two, three, four, five이며, 여기에는 총 3+3+5+4+4=19개의 글자가 사용되었다. 1에서 1000(one thousand)까지 숫자가 영어 단어로 적혀 있으면, 몇 개의 글자가 사용되는가?

주의: 빈칸, 하이픈은 세지 마시오. 예를 들어, 342(three hundred and forty-two)에는 23개 글자가 있으며, 115(one hundred and fifteen)에는 20개 글자가 있다. "and"는 영국식 영어에서 숫자를 셀 때 사용하는 것에 따른다.

--------------------------------------------------------------------------

처음으로 딕셔너리를 이용하여 문제를 해결하였다. 문제 자체는 20까지 각 숫자, 30 등 십단위, 백, 천까지 사전에 넣고 반복문과 조건문을 이용하면 되는 것이어서, 신경을 조금 써야되지만 까다로운 문제는 아니었는데 학교에서 미국식 영어로 배웠던 덕분에 'and'가 들어가는 규칙을 확인하는 것이 더 까다로운 부분이었다.

ㄱ솔직히 이야기하면 문제 해결하는 시간만큼 숫자 딕셔너리 작성하는 데 시간이 소요되었다.