어떤 수를 로마숫자로 나타낼 때는 여러가지 방식이 가능합니다 (아래 상자글 참조).
하지만, 특정 수를 표현하는 가장 최적의 방법은 항상 존재합니다.
| |
|
~ 로마 숫자에 대해 ~
전통적으로 로마숫자는 아래와 같은 단위를 사용합니다.
I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000
로마숫자의 구성 규칙에 대해서는 이런저런 이야기가 있지만, 사실 로마인들이 규칙으로 생각한 것은 하나 뿐입니다.
숫자 내의 문자는 크기가 작아지는 순으로 배치되어야 한다.
예를 들어 16은 XVI, XIIIIII, VVVI 처럼 세 가지로 나타낼 수 있는데, 대개는 문자를 가장 적게 쓰는 첫번째 방식이 선호됩니다.
"크기가 작아지는 순"이라고 명시한 것은 뺄셈에 의한 조합을 가능하게 하기 위한 목적입니다. 예를 들어 4는 IV와 같이 해서 5−1이 됩니다. 규칙에 의하면 숫자들은 작아지는 순이어야 하는데, 그렇지 않은 숫자가 중간에 끼어있다면 그것은 뺄셈을 위한 것임을 바로 알 수 있습니다. 19를 XIX 로 쓰면 이것은 X(10) + IX(9)로 해석할 수 있으며 위의 규칙에 부합하지만, IXX의 경우에는 그렇지 않으므로 잘못된 배열이 됩니다.
로마인들은 대개 가능하다면 적은 수의 문자를 사용하려고 했지만, 이것이 규칙으로까지 지켜지지는 않았습니다. 그 이후 중세께에 가서는 뺄셈에 대한 몇 가지 규칙이 추가되었습니다.
- 뺄셈을 구성하는 부분은 I, X, C로만 시작할 수 있다.
- I는 V, X 앞에만 올 수 있다.
- X는 L, C 앞에만 올 수 있다.
- C는 D, M 앞에만 올 수 있다
위 규칙에 따르면 49를 IL로 쓸 수는 없지만, XXXXVIIII, XXXXIX, XLVIIII, XLIX는 모두 올바른 표기입니다. 하지만 마지막 것이 최소 개수의 문자를 쓰고 있으므로 최적 표현이라 할 수 있습니다.
|
|
예를 들어 아래의 로마숫자들은 모두 16을 나타내는 올바른 예입니다.
IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI
이 중에서도 가장 마지막의 경우가 최소한의 문자를 쓰고 있으므로 가장 효율적입니다.
11KB 크기의 텍스트 파일 roman.txt에는 표기법상으로 올바르지만 꼭 최적화되었다는 보장은 없는 1만개의 로마숫자가 들어있습니다. 각 숫자의 문자들은 물론 작아지는 순으로 배열되어 있으며, (위 상자글에 언급된) 뺄셈을 위한 4가지 규칙을 준수합니다.
숫자들을 최적화된 형태로 모두 고쳐썼을 때, 줄어든 문자 수는 모두 몇 개나 됩니까?
참고 : 이 파일에 들어있는 모든 로마숫자에서 동일한 문자가 4개를 넘는 경우는 없습니다.
