CodeUp / Recursion(재귀) / 3733번 / 우박수 길이(3n + 1)(large) / C++

문제 설명   

콜라츠의 추측, 3n+1 문제, 우박수 문제라고 불리는 이 문제는 다음과 같다.

 

1, 어떤 자연수 n이 입력되면,

2. n이 홀수이면 3n+1을 하고,

3. n이 짝수이면 n/2를 한다.

4. 이 n이 1이 될때까지 2~3과정을 반복한다.

 

예를 들어 5는 5 → 16 → 8 → 4 → 2 → 1 이 된다.

 

여기서 5가 1이되기 위해 6개의 숫자를 나열하게 된다. 이것을 길이라고 하면 5의 길이는 6이된다.

시작수와 마지막 수가 입력되면 그 두 사이게 길이가 가장긴 우박수와 그 길이를 출력하시오.

 

입력

두 자연수 a, b가 공백으로 분리되어 입력된다. ( 1 <= a <= b <= 10,000,000 )

 

출력

a에서 b사이에 길이가 가장긴 우박수와 그 길이를 출력한다. 

만약 가장 긴 수가 두 개이상인 경우, 작은 숫자를 출력하시오.

 

입력 예시

1 10

 

출력 예시

9 20

 

#include <iostream>
using namespace std;

#define N 10000001

// 우박수가 int형의 범위을 넘을수 있으므로 long long int 사용
long long int arr[N] = { 0 };

long long int recursion(long long int k) {
	if (k == 1) return 1;

	if (k > 10000000) { // 지정된 수를 넘을경우 저장은 하지않고 카운트만 올림
		if (k % 2 == 1) return recursion(3 * k + 1) + 1;
		else if (k % 2 == 0) return recursion(k / 2) + 1;
	}

	if (arr[k] != 0) return arr[k]; // 메모이제이션

	else {
		if (k % 2 == 1) return arr[k] = recursion(3 * k + 1) + 1;
		else if (k % 2 == 0) return arr[k] = recursion(k / 2) + 1;
	}
}

int main() {
	int a, b;
	long long int most = arr[0];
	int idx = 0;
	cin >> a >> b;

	for (int i = a; i <= b; i++) {
		if(!arr[i]) recursion(i);

		if (most < arr[i]) { // 최댓값 찾기
			most = arr[i];
			idx = i; // 최댓값의 인덱스 저장
		}
	}

	cout << idx << " " << most << endl;
}

---

이번 문제는 시간과 오버플로우의 싸움이었다.

이렇게 범위가 클수록 재귀가 시간을 많이 잡아먹기에 메모이제이션을 사용해야 했고,

수가 크므로 int형보다 더 큰 long long int를 써줘야했다.

ex ) 주어진 수가 9999999일 경우 3k+1 이기 때문에 범위를 훨씬 뛰어넘는다.

      이럴 경우엔 저장을 하지않고, 카운트만 올려줬다.