Problem #014

오일러 알고리즘

🚩 문제 설명

오일러 알고리즘 #014

◾ 백만 이하로 시작하는 우박수 중에서 가장 긴 과정을 거치는 수를 구하는 문제.

우박수란? (hailstone sequence)
콜라츠 추측에서 나오는 수열이며 콜라츠 추측은 3n+1 추측, 울람 추측이라고 불리기도 한다.
1. n이 짝수 일때, n = n / 2
2. n이 홀수 일때, n = 3n + 1
이러한 과정을 거친 수를 우박수라고 하며
콜라츠의 추측은 임의의 자연수가 위와 같은 과정을 거쳐 항상 1이 된다는 추측이다.

 

 

---

 

 

📑 문제 풀이

#include <iostream>
#include <ctime>
#define ULL unsigned long long
using namespace std;

ULL go(ULL n)
{
	if (n <= 1) return 0;
	ULL temp;

	if (n % 2 == 0)
	{
		temp = go(n / 2) + 1;
	}
	else if (n % 2 != 0)
	{
		temp = go(3 * n + 1) + 1;
	}
	
	return temp;
}

int main()
{
	clock_t start, end;
	double time;

	start = clock();

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

	ULL max = 0;			// 가장 긴 과정을 구하기 위해
	ULL num;		
	ULL ans;

	for(int i=2; i<=1000000; i++)
	{
		num = go(i);

		if (num > max)
		{
			max = num;
			ans = i;
		}
	}
	
	cout <<"max: " << max << "\n";
	cout << "ans: " << ans << "\n";

	end = clock();
	time = (double)(end-start);
	cout << "\n\n" << time << "(ms)" << '\n';
	
	return 0;
}

💬 Point

👉 재귀함수 사용
👉 다이나믹 프로그래밍 문제
👉 D[n] = max( D[n/2], D[3n + 1] ) + 1

◾ 두 개의 연산을 사용하여 1로 도달하는 데 가장 긴 과정이 걸리는 수를 구해야한다.

◾ 재귀함수를 사용했다.

◾ 재귀함수는 과정의 수를 반환한다. (하나의 count 수를 반환하는 것과 같다.)

◾ 반복문을 돌아 100만까지 돈다.

◾ 수 하나하나씩 넣어가면서 각 수마다의 과정의 길이를 구한다.

◾ 최대값을 구한다.

 

💬 비슷한 문제

백준의 1로 만들기 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

---

 

 

But,

✅ 재귀가 너무 많이 쌓여서 오류가 생기기 때문에 long long 변수를 사용해서 답을 구했다.
✅ 굳이 재귀함수로 안풀었어도 됐을 것 같다.

➕ 풀이 사이트 첨부

https://www.mathblog.dk/project-euler-14/

Project Euler 14: Longest Collatz Sequence in C# | MathBlog

 

 

 

 

 

 

 

 

 

 

 

---