[C++]프로젝트 오일러 17번 문제&풀이 (1부터 1000까지 영어로 썼을 때 사용된 글자의 개수는?)

문제 17번

1부터 5까지의 수를 영어로 쓰면 one, two, three, four, five 이고,
각 단어의 길이를 더하면 3 + 3 + 5 + 4 + 4 = 19 이므로 사용된 글자는 모두 19개입니다.

1부터 1,000까지 영어로 썼을 때는 모두 몇 개의 글자를 사용해야 할까요?

참고: 빈 칸이나 하이픈('-')은 셈에서 제외하며, 단어 사이의 and 는 셈에 넣습니다.
  예를 들어 342를 영어로 쓰면 three hundred and forty-two 가 되어서 23 글자,
  115 = one hundred and fifteen 의 경우에는 20 글자가 됩니다.

 

접근방법

1. 숫자와 글자 갯수를 배열(array)에 담아 해당 수가 나오면 출력하는 구조로 진행.

2. 일단 배열에 글자 갯수를 넣어야 하는데, 1~20 / 30 / 40 / 50 / 60 / 70 / 80 / 90 / 100 / and / 1,000 총 30개를 배열에 넣고, 반복문에서 배열에 접근하여 가져다 쓰도록 할 것이다.

3. 먼저, 숫자가 주어지면 일의자리부터 차례로 벡터(vec)에 넣는다.

  → vec[0]은 항상 1의 자리, vec[1]는 항상 10의 자리, vec[2]는 항상 100의 자리가 되도록

4. 계산의 편리를 위해 1,000을 넘지 않아도 vec[3]까지 0으로 꽉 채워준다.

  → 4의 경우 4/0/0/0, 342의 경우 2/4/3/0, 1,000의 경우 0/0/0/1 이 되도록.

5. 나머지부터는 해당 숫자에 맞는 글자 갯수 배열을 조합해준다.

 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int _array[30]
{
    3,  //one       1   0
    3,  //two       2   1
    5,  //three     3   2
    4,  //four      4   3
    4,  //five      5   4
    3,  //six       6   5
    5,  //seven     7   6
    5,  //eight     8   7
    4,  //nine      9   8
    3,  //ten       10  9
    6,  //eleven    11  10
    6,  //twelve    12  11
    8,  //thirteen  13  12
    8,  //fourteen  14  13
    7,  //fifteen   15  14
    7,  //sixteen   16  15
    9,  //seventeen 17  16
    8,  //eighteen  18  17
    8,  //nineteen  19  18
    6,  //twenty    20  19
    6,  //thirty    30  20
    5,  //forty     40  21
    5,  //fifty     50  22
    5,  //sixty     60  23
    7,  //seventy   70  24
    6,  //eighty    80  25
    6,  //ninety    90  26
    7,  //hundred   100 27
    3,  //and       0   28
    8  //thousand   1000    29
};

int Alphabet(int num)
{
    int _num = num;
    int num_length = log10(_num) + 1;
    vector<int> vec;

    for (int i = num_length - 1; i >= 0; i--)
    {
        vec.push_back(_num % 10);
        _num /= 10;
    }

    for (int i = vec.size(); i < 4; i++)
    {
        vec.push_back(0);
    }

    int count = 0;

    if (vec[1] == 1)                            // 10 ~ 19
    {
        count += _array[10 + vec[0] - 1];
    }

    if (vec[1] != 1)
    {
        if (vec[0] != 0)
        {
            count += _array[vec[0] - 1];        // 1 ~ 9
        }
        else 
        {
            count = 0;                          // delete 20,30,40,50,60,70,80,90 
        }

        for (int i = 2; i < 10; i++)            // 20 ~ 99
        {
            if (vec[1] == i) count += _array[i + 17];
        }
    }
  
    if (vec[2] != 0)
    {
        if (vec[1] == 0 && vec[0] == 0)          //100, 200, 300 ...
        {
            for (int i = 1; i < 10; i++)
            {
                if (vec[2] == i) count = _array[i-1] + _array[27];
            }
        }
        else                                    // 101 ~ 199, ... 901 ~ 999
        {
            count += _array[vec[2] - 1] + _array[27] + _array[28];
        }
    }

    if (vec[3] != 0)                            // 1000
    {
        count = _array[0] + _array[29];
    }

    return count;
}


int main()
{
    /*int num = 342;
    int length = Alphabet(num);
    
    cout << "Number Length : " << num << " / " << length << endl;*/

    int con = 0;

    for (int num = 1; num <= 1000; num++)
    {
        con += Alphabet(num);
        cout << num << " : " << Alphabet(num) << endl;
    }

    cout << "Answer is : " << con << endl;
    
    return 0;
}

참고

https://github.com/mannlim/ProjectEuler

mannlim/ProjectEuler