Problem 17 : Number letter counts (5%)

Description

original

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

간략해석

수를 1부터 1000까지 셀 때, 글자수를 세시오

Idea & Algorithm

naive idea

이 문제의 경우에는 두 가지 방법이 존재한다.

각 자릿수별 단어를 카운팅하여 반복문을 사용하여 각 단어를 실제로 만들면 된다. 좀 더 구체적으로 설명하면 123의 경우에는 100 + 20 + 3으로 분해하여 워드를 카운팅하면 된다.
전체 수에서 각 단어의 개수를 미리 카운팅하여 $O(1)$에 계산한다.

아래는 2번 방법으로 문제를 해결한 C코드다. 각 카운팅은 주석처리 하였다.

advanced idea

source code

방법 2의 코딩

#include <stdio.h>
// one two three four five six seven eight nine
// 3 3 5 4 4 3 5 5 4 = 36
// ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen
// 3 6 6 8 8 7 7 9 8 8 = 70
// twenty thirty forty fifty sixty seventy eighty ninety
// 6 6 5 5 5 7 6 6 = 46

int main(){
    int tot = 0;
    tot += 36 * 9 + 70 + 460;
    tot = tot*10; // 1~99 * 10
    tot += 3 * 99 * 9; // and
    tot += 7*900; // hundred
    tot += 36 * 100; //front hundred
    tot += 3 + 8; // one thousand
    printf("%d",tot);
}

방법 1의 코딩

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string ones[10] = {"", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
string ttens[10] = {"ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
string tens[10] = {"", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
string hundred = "hundred";
string thousand = "thousand";

string itow(int n){
    string ret;
    if(n==1000) return ones[1] + thousand;
    if(n/100) ret += ones[n/100] + hundred;
    if(n/100 && n%100) ret += "and";
    if((n%100)/10>=2){
        ret += tens[(n%100)/10];
        ret += ones[n%10];
    }
    else if((n%100)/10==1) ret += ttens[n%10];
    else ret += ones[n%10];
    return ret;
}

int main(){
    int sum = 0;
    cout << itow(123) << endl;
    for(int i =1 ; i <= 1000 ; i++){
        sum += itow(i).size();
    }
    cout << sum;
}

Problem 017