Problem #017

오일러 알고리즘

🚩 문제 설명

오일러 알고리즘 #17

◾ 1부터 1000까지 영어로 썼을 때 사용된 글자의 개수를 구하는 문제

◾ 빈칸이나 하이폰은 셈에서 제외한다.

◾ 단어 사이의 and는 셈에 넣는다.

ex) 342 -> three hundred and forty-two

 

 

---

 

 

📑 문제 풀이

#include <iostream>
using namespace std;

int num[1000];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	//	수 넣기
	//	1 - 19 까지 숫자
	num[1] = 3; num[2] = 3; num[3] = 5;
	num[4] = 4; num[5] = 4; num[6] = 3;
	num[7] = 5; num[8] = 5; num[9] = 4;
	num[10] = 3; num[11] = 6; num[12] = 6;
	num[13] = 8; num[14] = 8; num[15] = 7;
	num[16] = 7; num[17] = 9; num[18] = 8; num[19] = 8;

	// 10 단위 숫자	twenty - ninety
	num[20] = 6, num[30] = 6; num[40] = 5;
	num[50] = 5; num[60] = 5; num[70] = 7;
	num[80] = 6; num[90] = 6;

	//	1000
	num[1000] = 11;


	//	그 이외의 수 넣기
	//	21 - 99
	for (int i = 2; i <= 9; i++)
	{
		for (int j = 1; j <= 9; j++)
		{
			num[i * 10 + j] = num[i * 10] + num[j];
		}
	}

	//	100 - 999
	for (int i = 1; i <= 9; i++)
	{
		for (int j = 0; j <= 99; j++)
		{
			//	100단위 예외 처리
			if ((i * 100 + j) % 100 == 0)
				num[i * 100 + j] = num[i] + 7;		// hundred = 7
			else
				num[i * 100 + j] = num[i] + 10 + num[j];	// hundred and = 10
		}
	}


	//	합 구하기
	int sum = 0;
	for (int i = 1; i <= 1000; i++)
	{
		sum += num[i];
		//cout <<i<<","<< num[i] << '\n';
	}

	cout << sum << '\n';
	return 0;
}

💬 Point

👉 영어글자 길이 배열 값으로 미리 넣어놓기

◾ 우선 1 ~ 19까지의 숫자들의 영어글자의 길이를 구해서 해당 배열에 넣어준다.

◾ 10단위의 수도 마찬가지로 넣어준다.

◾ 1000도 예외적이므로 넣어준다.

◾ 그 이외의 수들은 위 수들의 조합으로 나온다.

◾ 각자 반복문을 돌아 구해준다.

◾ 글자들의 길이를 합으로 구해준다.

 

 

---

 

 

But,

✅ 케이스를 나눠서 풀었는데 다른 많은 방법이 또 있을 것이다.

➕ 풀이 사이트 첨부

https://www.mathblog.dk/project-euler-17-letters-in-the-numbers-1-1000/

Project Euler 17: Letters in the numbers 1-1000 in C# | MathBlog

➕ 영어 참고 사이트

https://ilikeen.tistory.com/2184

영어 숫자 읽는 법 표로 간단 정리 (숫자 영어로 읽기)

 

 

 

 

 

 

 

 

 

 

 

---