1872 로마숫자

주어진 문장에서 한 문자씩 따와 가장 큰 로마숫자를 만드는 문제이다.
처음에 도전했다가 포기하고 다른분(pichulia)의 도움을 받아 다시 도전하여 풀게 되었다.

이 문제는 로마숫자의 규칙을 잘 이해해야 풀 수 있다.

처음엔 X문자는 최대 3번밖에 못쓰는 줄 알고 있었으나,
XXXIX 같은 경우가 존재했다. (다른분의 도움으로 반례를 찾음)

이 문제를 푸는 방법은 우선,
로마숫자의 가장 큰 수 M부터 가장 작은 수 I 까지 반복하면서 문자열을 살펴본다.
M을 제외한 모든 로마 숫자에는 사용될 수 있는 갯수가 제한되어있다. 따라서 제한된 숫자를 기록하는 배열을 하나 잡는다.
각 로마숫자에 맞는 문자가 나타나고, 횟수가 남아있으면, 그 문자를 고른다.
그리고 다음 반복은 그 문자의 위치부터 시작하기위해 변수(m)를 하나 둔다.

그렇게 돌다가 횟수가 0인데 다시 문자가 나타나는 경우, 그리고 그 문자가 X와 C일때
그 위치부터 m까지 되돌아가면서 IX 나 XC를 만들 수 있는지 살펴본다.
만약 가능하면 그 문자를 추가 한 후, m값을 다시 조정하고
그 문자의 횟수는 -1로 바꾼다.(IX는 한번만 나와야 하므로)
그 문자의 다음 문자와 그 다음 문자의 횟수를 0으로 만든다.
예를들어 XC를 만들었으면, L과 X의 횟수를 0으로 만드는 것이다.
여기서 X의 횟수가 0이 됬지만 IX는 만들 수 있다는것에 주목하자.

이것은 로마숫자의 규칙에 의한것이며, X와 C일때만 이렇게 해주는 것은,
이 경우를 제외한 경우에서 규칙에 맞는 최대값이 존재하지 않기 때문이다.

위와 같은 방법으로 반복을 마쳤다면, 고른 문자들을 10진법으로 바꿔주고 출력해주면 된다.

소스