Problem #008

오일러 알고리즘

🚩 문제 설명

오일러 알고리즘 #08

◾ 1000자리 숫자 안에서 이어지는 5자리의 곱 중에서 최댓값을 찾는 문제

◾ 5개씩 끊으면 되겠구나 생각을 해본다.

◾ 1000자리 숫자는 저렇게 주어진다.

 

 

---

 

 

📑 문제 풀이

#include <iostream>
#include <string>
using namespace std;

string num = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

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

	int max=0;		//최댓값
	int n;				

	for (int i = 0; i < 996; i++)
	{
		int sum = 1;
		for (int j = i; j < i + 5; j++)
		{
			n = num[j] - '0';				//char을 int로
			sum *= n;
		}
		if (max < sum) max = sum;
	}
	cout << max << "\n";

	return 0;
}

💬 Point

👉 문자열을 사용한다.

◾ 1000자리에서 5자리씩 곱하는 것이니 1에서 995 인덱스까지만 돌아줘도 된다.

◾ 큰 숫자가 들어가므로 문자열을 사용했다.

◾ 한칸씩 인덱스를 이동하면서 해당 인덱스부터 시작하여 + 5까지 반복문을 돌아준다.

• 그리고 sum 변수를 사용하여 해당 인덱스에 해당하는 숫자를 곱해준다.
• 돌아가는 반복문의 로직은 아래의 표와 같다.

i	j (i부터 시작해서 i+5까지)	num[j]
0	0, 1, 2, 3, 4	7, 3, 1, 6, 7
1	1, 2, 3, 4, 5	3, 1, 6, 7, 1
2	2, 3, 4, 5, 6	1, 6, 7, 1, 7

char - '0' 을 해주면 int 타입이 된다.
ex) num[0] - '0' = 7

◾ max 라는 최댓값 변수를 둬서 최댓값을 찾는다.

 

 

---

 

 

But,

✅ 반복문을 두개씩 주지 않고 하나만 사용해서 풀 수 있었다면 좋았을 것 같다.

➕ Solution 풀이 사이트 첨부

https://www.mathblog.dk/solution-to-problem-8-of-project-euler/

Solution for Problem 8 of Project Euler in C# | MathBlog

 

 

 

 

 

 

 

 

 

 

---