Project Euler Problem 17
解説
解法(C++)
9999までは解けることになっています。
#include <iostream>
#include <math.h>
#define MAX_LENGTH 99999
using namespace std;
/******************************************/
/*Author: pb10001 */
/*Date:2018/7/17 */
/* */
/*Project Euler Problem 17を解くプログラム*/
/******************************************/
int solve(int n);//問題を解く関数
int A[MAX_LENGTH];//英単語の長さ
int S[MAX_LENGTH];//英単語の長さの総数
int D[MAX_LENGTH];//桁に対する単語の長さ
int main(void){
/* 初期値を設定 */
A[0] = 0;
A[1] = 3; // one
A[2] = 3; // two
A[3] = 5; // three
A[4] = 4; // four
A[5] = 4; // five
A[6] = 3; // six
A[7] = 5; // seven
A[8] = 5; // eight
A[9] = 4; // nine
A[10] = 3; // ten
A[11] = 6; // eleven
A[12] = 6; // twelve
A[13] = 8; // thirteen
A[14] = 8; // fourteen
A[15] = 7; // fifteen
A[16] = 7; // sixteen
A[17] = 9; // seventeen
A[18] = 8; // eighteen
A[19] = 8; // nineteen
A[20] = 6; // twenty
A[30] = 6; // thirty
A[40] = 5; // forty
A[50] = 5; // fifty
A[60] = 5; // sixty
A[70] = 7; // seventy
A[80] = 6; // eighty
A[90] = 6; // ninety
S[0]=A[0];
for(int i=1;i<=19;i++){
S[i]=S[i-1]+A[i];
}
for(int i=20;i<MAX_LENGTH;i++){
S[i]=-1;
}
D[2]=7;//hundred
D[3]=8;//thousand
int n;
cin >> n;//標準入力から整数を受け取る
cout<<"答え: "<<solve(n)<<endl;
}
int solve(int n){
if(S[n]>=0) return S[n];//計算済みならその値を返す
if(n<100){
/* 2桁の場合 */
S[n]=solve(n-n%10-1)+S[n%10]+A[n-n%10]*(n%10+1);
}
else{
/* 3桁以上の場合 */
int digitLength = 2;
while(n>=pow(10, digitLength)) digitLength++;
digitLength--;
int num = pow(10, digitLength);
S[n]=n%num==0?solve(n-1)+A[n/num]+D[digitLength]:solve(n-n%num)+solve(n%num)+(n%num)*(A[n/num]+D[digitLength]+3);
}
return S[n];
}