C 언어로 정수를 로마 숫자로 변환하는 방법

10진수 n이 주어졌을 때, 이를 로마 숫자(Roman Numeral)로 변환하는 프로그램을 만들어 보겠습니다. 입력 값 n은 1부터 4000 사이의 범위를 가집니다. 먼저 주요 로마 숫자와 그에 대응하는 값을 살펴보겠습니다.

예를 들어 n = 859라면, 변환된 로마 숫자는 DCCCLIX가 됩니다.

문제 해결 접근 방식

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 로마 숫자 기호와 그에 대응하는 값을 함께 저장하는 배열(이하 nume 배열)을 정의합니다.
• 재귀(recursion) 방식으로 문제를 해결하며, decToRoman() 함수가 nume 배열과 변환할 숫자 num을 인자로 받습니다.
• decToRoman() 함수의 동작 방식은 다음과 같습니다.
• num이 0이 아니라면 다음을 반복합니다.
  • nume 배열에서 num보다 크지 않은 최대 값을 찾아 max에 저장합니다.
  • max에 대응하는 로마 숫자 기호를 결과 문자열에 추가합니다.
  • num에서 max 값을 뺍니다.
  • decToRoman(nume, num)을 재귀 호출합니다.

구현 예제

다음 C 언어 구현 예제를 통해 더 쉽게 이해할 수 있습니다.

#include<stdio.h>
typedef struct{
    char *sym;
    int val;
}numeral;
int maxNume(numeral *nu, int num){
    int i, index;
    for(i = 0; i<15; i++){//배열에는 15개의 기호가 있음
       if(nu[i].val <= num)
          index = i;
    }
    //num보다 크지 않은 가장 큰 값의 기호 인덱스 반환
    return index;
}
void decToRoman(numeral *nu, int num){
    int max;
    if(num != 0){
       max = maxNume(nu, num);
       printf("%s", nu[max].sym);
       num -= nu[max].val;//숫자 감소
       decToRoman(nu, num);//재귀적으로 기호 출력
    }
}
main(){
    int number;
    numeral nume[15] = {{"I",1},{"IV",4},{"V",5},{"IX",9}, {"X",10},{"XL",40},{"L",50},{"XC",90},
{"C",100},{"CD",400},{"D",500},{"CM",900},{"M",1000},{"MMMM",4000},{"V'",5000}};
    printf("Enter a decimal number: ");
    scanf("%d", &number);
    if(number >0 && number <= 5000){//입력값 범위 검사
       printf("The Roman equivalent of %d is ", number);
       decToRoman(nume, number);
    }
    else{
       printf("Invalid Input");
    }
    printf("
");
}

입력

570
3574

출력

DLXX
MMMDLXXIV

위 실행 결과를 보면 570은 DLXX(500 + 50 + 20)로, 3574는 MMMDLXXIV(3000 + 500 + 50 + 20 + 4)로 올바르게 변환된 것을 확인할 수 있습니다. 이처럼 탐욕적(greedy) 선택과 재귀 호출을 조합하면 로마 숫자 변환 문제를 간결하게 해결할 수 있습니다.