[C/C++] 프로젝트 오일러 #89 Roman Numerals(계산)

이번 문제는 로마 숫자와 관련된 것입니다.

 

프로젝트 오일러 문제 89: 로마 숫자 최적화

로마 숫자는 전통적으로 다음과 같은 문자 조합으로 이루어집니다:

• I = 1
• V = 5
• X = 10
• L = 50
• C = 100
• D = 500
• M = 1000

그리고 로마 숫자는 보통 큰 숫자가 작은 숫자보다 앞에 오는 방식으로 작성됩니다. 예를 들어, VII는 7입니다(5 + 1 + 1). 하지만 더 작은 로마 숫자 기호가 더 큰 숫자 앞에 오면 그 값을 빼는 방식으로 표현할 수 있습니다. 예를 들어, IV는 4이고, IX는 9입니다.

문제:

주어진 로마 숫자를 가장 간단하게 표현했을 때, 몇 개의 문자를 절약할 수 있는지 계산하는 것입니다.

1. 로마 숫자들을 최적화하여 가장 짧은 형태로 바꿉니다.
2. 변환 전의 로마 숫자와 변환 후의 로마 숫자 사이에서 줄어든 문자 수를 구합니다.

예를 들어, XIIII는 XIV로 줄일 수 있고, VVVIIII는 XVIII로 줄일 수 있습니다.

목표: 파일에 여러 개의 로마 숫자가 있을 때, 각 숫자를 가장 짧게 줄였을 때 절약할 수 있는 문자 수의 총합을 구하는 것입니다.

 

roman numerials

 

이 코드는 파일에 있는 여러 개의 로마 숫자 문자열을 읽어서, 각 로마 숫자를 최적화했을 때 절약할 수 있는 문자 수의 총합을 계산하는 프로그램입니다. p089_roman.txt라는 파일에서 로마 숫자를 읽고, 각 숫자에 대해 최적화하여 절약된 문자 수를 구한 뒤 그 총합을 출력합니다. 주요 함수와 흐름을 설명하겠습니다.

주요 구성 요소

1. 파일 읽기 및 초기화:

FILE *fi = fopen(FN, "r");
char buf[128];

프로그램은 p089_roman.txt 파일에서 로마 숫자를 한 줄씩 읽습니다. 각 줄마다 buf 배열에 로마 숫자 문자열이 저장됩니다.

2. 루프와 error 함수 호출:

while( fgets(buf, 128, fi) )
    ans += error(buf);

파일에서 각 줄을 읽어와 error 함수에 전달하고, error 함수가 반환하는 절약된 문자 수를 ans에 누적하여 총합을 계산합니다.

3. error 함수:
error 함수는 주어진 로마 숫자 문자열을 최적화했을 때 절약된 문자의 개수를 반환합니다. 이 함수는 다음 두 가지 작업을 수행합니다:
• 로마 숫자를 정수 값으로 변환하여 이를 분석하고
• 최적화된 형태와의 문자 수 차이를 계산합니다.

로마 숫자를 정수 값으로 변환

1. 숫자 계산:

for( c = 0 ; ; c++ )
{
    // 각 문자에 따라 값을 누적
}

str 문자열을 순회하며 각 문자가 나타내는 값을 더해 n에 누적합니다. 예를 들어, M이 있으면 1000을 더하고, D가 있으면 500을 더합니다.

2. 특수 규칙 적용:

if( last == 'C' ) n -= 200;

숫자를 더하는 과정에서 로마 숫자 표기법의 특수 규칙을 적용하여, 빼야 할 경우(IV, IX, XC 등)에는 값에서 일정 값을 빼 줍니다.

절약 문자 계산

1. 천의 자리 문자 계산:

c -= n/1000;

이 줄에서는 최적화된 로마 숫자 표기법으로 사용할 수 있는 문자 수를 계산합니다. 천 단위의 문자(M)는 n/1000에 따라 줄일 수 있습니다.

2. 절약 문자 수 계산:

const int t[] = { 0, 1, 2, 3, 2, 1, 2, 3, 4, 2 };

여기서 t 배열은 각 자리수마다 최적화된 로마 숫자 표기법에서 필요한 최소 문자의 수를 의미합니다. 예를 들어, 1은 I 하나만 필요하므로 1, 4는 IV로 나타낼 수 있으므로 2입니다.

3. 최종 문자 수 계산:

c -= t[r];

남은 n의 자리 수에 대해, 배열 t의 값을 참조하여 필요한 문자의 수를 빼줍니다. 이를 통해 원래 문자열과 최적화된 문자열 간의 차이를 계산할 수 있습니다.

출력

마지막으로, 누적된 ans 값을 출력하여 절약된 문자 수의 총합을 표시합니다:

printf("ans = %d\n", ans);

요약

이 프로그램은 각 로마 숫자를 파일에서 읽어와서 이를 정수로 변환하고, 최적화된 로마 숫자 표기법으로 절약된 문자 수를 계산하여 총합을 출력하는 구조로 되어 있습니다.

 

설명한 소스의 전체 내용입니다.

//------------------------------------------------
//    Project Euler #89 - Roman Numerials
//        - by Aubrey Choi
//        - created at 2015-03-12
//------------------------------------------------
#include <stdio.h>

#define    FN    "p089_roman.txt"

int error(const char *str);

int main()
{
    int ans = 0;

    FILE *fi = fopen(FN, "r");
    char buf[128];
    while( fgets(buf, 128, fi) )
        ans += error(buf);
    fclose(fi);
    printf("ans = %d\n", ans);
}

int error(const char *str)
{
    int n = 0;
    int c;
    int last = 0;
    const int t[] = { 0, 1, 2, 3, 2, 1, 2, 3, 4, 2 };
    for( c = 0 ; ; c++ )
    {
        if( str[c] == 'M' )
        {
            n += 1000;
            if( last == 'C' ) n -= 200;
        }
        else if( str[c] == 'D' ) 
        {
            n += 500;
            if( last == 'C' ) n -= 200;
        }
        else if( str[c] == 'C' )
        {
            n += 100;
            if( last == 'X' ) n -= 20;
        }
        else if( str[c] == 'L' )
        {
            n += 50;
            if( last == 'X' ) n -= 20;
        }
        else if( str[c] == 'X' )
        {
            n += 10;
            if( last == 'I' ) n -= 2;
        }
        else if( str[c] == 'V' )
        {
            n += 5;
            if( last == 'I' ) n -= 2;
        }
        else if( str[c] == 'I' ) n += 1;
        else break;
        last = str[c];
    }
    c -= n/1000;
    n %= 1000;
    while( n )
    {
        int r = n%10;
        c -= t[r];
        n /= 10;
    }
    return c;
}