[C/C++] 코드업(codeup) 3733번 우박수 길이 (3n+1) (large)

▽문제 바로가기

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

우박수 길이 (3n+1) (large)

---

입력

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

 

출력

a에서 b사이에 길이가 가장긴 우박수와 그 길이를 출력한다. 만약 가장 긴 수가 두 개이상인 경우, 작은 숫자를 출력

 

문제 풀이

 

우박수 길이를 구하는 문제입니다. 입력값의 범위는 천만이라는 숫자입니다. 컴퓨터에게 천만이라는 수는 별거 아닙니다. 하지만, 입력이 범위인 만큼 메모이제이션을 활용하면 계산속도를 더 올릴 수 있을 겁니다.

 

※ 메모이제이션 범위

입력수는 천만이라는 숫자이지만 계산중에 천만을 훌쩍 넘어버립니다. 예를 들어, 9,999,999라는 홀수는 3이 곱해지고 1이 더해지므로 거의 3천만에 근접합니다. 그 이후 계산을 통해 더 큰 수가 될 수도 있습니다.

그러면 배열의 수를 넉넉하게 1억?

저는 1억의 배열을 잡으니 메모리 초과로 나왔습니다.

 

저의 해결법은 배열을 천만까지만 잡고 더 큰 숫자가 재귀될 때는 그냥 메모를 하지 않는 것입니다. 천만이 넘는 경우가 종종 발생하겠지만 메모를 하지 않더라도 성능에 크게 영향을 줄 것 같진 않습니다. 이렇게 하여 세그먼트 에러(segmentation error)도 피할 수 있고 메모리 초과도 피할 수 있습니다.

 

#include <stdio.h>

long long int memo[10000001]={0};	//메모 
long long int max = 0;	//최대 길이 
int locate = 0;	//최대 길이의 수
 
//최대 길이및 최대 길이 수 구하는 함수
long long int mymax(long long int a, long long int b, int c){
	if(a>b){
		locate = c;
		return a;
	}
	else return b;
}

//우박수 구하는 재귀함수
long long int recur(long long int a){
	if(a==1) return 1;
	
	//천만이 넘는 큰 수라면(메모배열넘음) 메모안함
	if(a>10000000){
		if(a%2==0) return recur(a/2) + 1;
		else return recur(a*3+1) +1;
	}
	
	//메모가 되어 있다면 함수 호출 말고 메모값 리턴
	if(memo[a]!=0) return memo[a];
	
	//메모, 재귀 호출
	else{
		if(a%2==0) return memo[a] = recur(a/2) + 1;
		else return memo[a] = recur(a*3+1) + 1;
	}
}

int main(){
	
	int a, b;
	scanf("%d %d", &a, &b);
	
	//주어진 범위 호출
	while(a<b+1){
		long long int temp = recur(a);
		max = mymax(temp, max, a);
		++a;
	}
	
	printf("%d %lld\n", locate, max);
	
	return 0;
}