키큰개발자

문제링크)

- http://codeup.kr/problem.php?id=3733

해결방법)

어떤 임의의 자연수 n 을 입력받고 홀수 or 짝수 일때의 각각의 규칙에 따라 재귀함수를 호출한다.

이때 재귀함수 호출 횟수가 몇번인지가 문제에서 말한 우박수의 길이가 되고 이것을 구하면 된다.

규칙은 다음과 같다.

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

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

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

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

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

여기서 생각해야할 부분이 있는데, 입력이 자연수 a, b 구간으로  1<= a <= b <= 10,000,000 의 아주 큰 범위를 갖는다.

그래서 이 문제가 large 버전으로 이름이 붙여진 것 같다.

이 큰 값의 범위 입력을 풀기 위해서 대표적인 방법으로 메모이제이션을 써서 시간복잡도를 줄여야 겠다는 생각을 했다.

그리고 코딩하면서 알게 된것이 배열을 천만으로 선언할 수 있다는 것을 알 수 있었다. 너무 비효율적이라 생각되는데 무튼 문제만 푼다면야...하고 일단 넘어가자.

메모이제이션을 할때 천만으로만 하기 때문에 n이 홀수여서 천만의 값을 넘어간다면 이는 따로 조건을 추가해서 메모이제이션을 안하고 다음 재귀함수를 그냥 호출 하는 방식으로 구해보았다.