RSS Feed

로마숫자 최적화하기

Problem 89

출제 일시 : 2012-04-26 19:47:06

어떤 수를 로마숫자로 나타낼 때는 여러가지 방식이 가능합니다 (아래 상자글 참조).
하지만, 특정 수를 표현하는 가장 최적의 방법은 항상 존재합니다.

~ 로마 숫자에 대해 ~

전통적으로 로마숫자는 아래와 같은 단위를 사용합니다.

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의 경우에는 그렇지 않으므로 잘못된 배열이 됩니다.

로마인들은 대개 가능하다면 적은 수의 문자를 사용하려고 했지만, 이것이 규칙으로까지 지켜지지는 않았습니다. 그 이후 중세께에 가서는 뺄셈에 대한 몇 가지 규칙이 추가되었습니다.

  1. 뺄셈을 구성하는 부분은 I, X, C로만 시작할 수 있다.
  2. I는 V, X 앞에만 올 수 있다.
  3. X는 L, C 앞에만 올 수 있다.
  4. C는 D, M 앞에만 올 수 있다

위 규칙에 따르면 49를 IL로 쓸 수는 없지만, XXXXVIIII, XXXXIX, XLVIIII, XLIX는 모두 올바른 표기입니다. 하지만 마지막 것이 최소 개수의 문자를 쓰고 있으므로 최적 표현이라 할 수 있습니다.

예를 들어 아래의 로마숫자들은 모두 16을 나타내는 올바른 예입니다.

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

이 중에서도 가장 마지막의 경우가 최소한의 문자를 쓰고 있으므로 가장 효율적입니다.

11KB 크기의 텍스트 파일 roman.txt에는 표기법상으로 올바르지만 꼭 최적화되었다는 보장은 없는 1만개의 로마숫자가 들어있습니다. 각 숫자의 문자들은 물론 작아지는 순으로 배열되어 있으며, (위 상자글에 언급된) 뺄셈을 위한 4가지 규칙을 준수합니다.

숫자들을 최적화된 형태로 모두 고쳐썼을 때, 줄어든 문자 수는 모두 몇 개나 됩니까?

참고 : 이 파일에 들어있는 모든 로마숫자에서 동일한 문자가 4개를 넘는 경우는 없습니다.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.