[Codeup] 3733. 우박수 길이 (3n+1) (Large)

1. 문제 링크

https://codeup.kr/problem.php?id=3733

코드업

 

2. 문제 풀이

1 <= a <= b <= 10,000,000 으로 상당히 크다.  중간 과정을 생략하기 위한 계산이 필요하다.

지나온 경로에 대한 계산을 위해 재귀 탐색을 진행하였고, 메모이제이션으로 값을 계산해두어 연산 횟수를 줄였다.

3. 아이디어

1. 이 문제의 핵심은 각 시작 수마다 1까지 직접 계산하면 중복 연산이 많이 발생한다는 점이다.
2. 따라서 어떤 수 n에서 1까지 도달하는 수열의 길이 length[n]을 저장해둔다.
3. 연산 과정에서 같은 n을 다시 만나면 저장된 값을 재사용한다.
4. 단, 수열을 앞에서부터 진행하는 동안에는 중간값의 length가 아직 확정되지 않는다.
    4-1. 반복문으로 구현한다면 지나온 경로를 path에 저장한 뒤, 이미 계산된 값을 만났을 때 역순으로 length를 채워야 한다.
    4-2. 재귀로 구현하면, 호출 과정에서 반환 해주는 것으로 path 역할을 해줄 수 있다. 즉, return 과정에서 length[n] = length[next] + 1 형태로 자연스럽게 메모이제이션이 가능하다.
5. 중간 값이 커질 수 있으므로, long long int를 사용하고, 메모리 크기 제한을 고려하여, LIMIT를 두어 배열 범위 안의 값만 캐싱해 준다.

 

4. 구현

※ C++ Source Code

#include <iostream>
#define LIMIT 10000000
using namespace std;
int length[LIMIT];

int three_n(long long int in)
{
	if (in < LIMIT && length[in] != 0) // 계산됨.
	{
		return length[in];
	}

	long long int next_value;
	if (in % 2 == 1) next_value = 3 * in + 1;
	else  next_value = in / 2;

	int result = three_n(next_value) + 1;
	
	if (in < LIMIT)
	{
		length[in] = result;
	}
	return result;
}
int main(void)
{
	int n;
	int a, b;
	int temp;

	int ans_number = 0;
	int ans_length = 0;

	length[1] = 1; // 1의 수열의 길이
	cin >> a >> b;
	for (int i = a; i <= b; i++)
	{
		temp = three_n(i);
		if (temp > ans_length)
		{
			ans_number = i;
			ans_length = temp;
		}
	}
	cout << ans_number << " " << ans_length;
}