[C/C++] 백준 #2608 로마 숫자(구현)

로마숫자 표기법은 아라비아 숫자 대신 제일 많이 사용되는 숫자 표현법이죠.  그래서 대략 100 미만의 숫자들은 표기할 줄 알지만, 그 이상 숫자들은 잘 모릅니다.  

 

roman numbers 1~100

 

아라비아 숫자들은 숫자들의 위치에 따라서 숫자의 단위가 크게 달라지지만, 로마 숫자는 영문자에 따라서 단위가 정해져 있습니다.  하지만 여기에 빼기 개념도 있어서 IV = 5 - 1 = 4 와 같이 단위 문자의 위치에 따라서 빼기가 성립합니다.  IIII 라고 표현하면, 문자길이가 4이지만 IV라고 표현하면 문자길이가 2이기 때문에 두번째 방식을 택합니다.  IIV 와 같은 개념은 존재하지 않기 때문에 로마 숫자를 십진법으로 변환하기 위해서는 하나 앞이라는 개념만 이해하면 됩니다.  VX와 같이 5단위 문자인 V가 10단위 문자인 X 앞에 나오는 경우도 없습니다.  로마 숫자는 10진법을 기반으로 하는 숫자입니다.

 

https://www.acmicpc.net/problem/2608

2608번: 로마 숫자

 

특별한 알고리즘이 필요한 문제는 아니고 구현을 얼마나 잘 할 수 있느냐의 문제입니다.  시간복잡도도 고민할 이유는 없습니다.  순차탐색으로 계산할 수 있으니까요.

 

제가 푼 핵심은 I 의 경우 1을 더하고, V나 X 앞에 I가 있으면 2를 뺌으로써 전체적으로 1이 차감된 상태가 되게 합니다.

예를 들어서 64를 의미하는 LXIV를 생각해보죠.  L을 읽고 50을 더합니다.  X를 읽고 10을 더합니다.  I를 읽고 1을 더합니다.  V를 읽고 5-2=3을 더합니다.  50+10+1+3 = 64 라는 결과를 얻은 것이죠.  여기서 중요한 것은 X, V, L 등 5 이상 단위 숫자들의 앞에 그 바로 아래 단계의 문자가 있을 때에는 2배 해서 빼주는 것이 핵심입니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2608
//        - by Aubrey Choi
//        - created at 2019-08-08
//------------------------------------------------
#include <stdio.h>

int to(const char s[])
{
    int n=0, p=0;
    for(int i=0; s[i]; i++)
    {
        if(s[i]=='M') n+=1000-(p=='C')*200;
        else if(s[i]=='D') n+=500-(p=='C')*200;
        else if(s[i]=='C') n+=100-(p=='X')*20;
        else if(s[i]=='L') n+=50-(p=='X')*20;
        else if(s[i]=='X') n+=10-(p=='I')*2;
        else if(s[i]=='V') n+=5-(p=='I')*2;
        else n++;
        p=s[i];
    }
    return n;
}

void put(int t, char a, char b, char c)
{
    if(t==9) { putchar(c); putchar(a); return; }
    if(t==4) { putchar(c); putchar(b); return; }
    if(t>=5) { putchar(b); t-=5; }
    while(t--) putchar(c);
}

int main()
{
    char a[20], b[20];
    int na, nb, nc, t;
    scanf("%s%s", a, b);
    na = to(a); nb = to(b); nc=na+nb;
    printf("%d\n", nc);
    t = nc/1000; nc%=1000; put(t, ' ', ' ', 'M');
    t = nc/100; nc%=100; put(t, 'M', 'D', 'C');
    t = nc/10; nc%=10; put(t, 'C', 'L', 'X');
    put(nc, 'X', 'V', 'I');
    putchar('\n');
    return 0;
}