014. Longest Collatz Sequence(짝수이면 n/2, 홀수는 3n+1인 변환에서 1이될 때까지 몇 번 변환인지 구하기)

 

 

 

​문제 (English)

The following iterative sequence is defined for the set of positive integers:

$n \rightarrow n/2$ (n is even)

$n \rightarrow 3n + 1$ (n is odd)

 

Using the rule above and starting with 13, we generate the following sequence:

$13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$.

It can be seen that this sequence (starting 13 and finishing at 1 ) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

 

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

 

Answer:837799

문제 분석

---

어떤 수 n에 대해서, 짝수일 때는 $n/2$, 홀수일 때는 $3n+1$로 변하면, 끝내는 1로 수렴하게 되는데, 이때 1까지 도달하려면 몇 번 변하게 되는지를 구하는 문제. 

N=10이면 10 이하의 수 n에 대해서 각각 1이 될 때까지의 변환 회수를 p라고 한다면, 이 p가 가장 클 때의 n을 출력하면 됨

 

N이 주어지면, N이하의 모든 수에 대해서 1이 될때까지 몇 번 변하면 되는지를 다 구해야 함.

 

예를 들어 5에 대해서는,

$5 \rightarrow 3\times 5 + 1 = 16 \rightarrow 16/2 = 8 \rightarrow 8/2=4 \rightarrow 4/2=2 \rightarrow 2/2 =1$

총 6번의 변환이 있고, 이러한 변화하는 수를 나타내는 배열을 C(i)라고하면, C(5)=6

 

Euler 사이트에 있는 문제에서 예를 든 13에 대해서는 C(13)=10

 

근데, 13이 변화는 과정에서 보면, 중간에 5인 경우가 있는데, 이 5의 경우는 이미 구한 C(5)=6을 이용하면, 5 이후에 변환과정을 다 따라갈 필요가 없음. 즉, 메모이제이션 기법을 사용하면 코드 수행시간을 단축시킬 수 있다.

 

풀이 1 

---

문제에서 주어진 변환 규칙을 그대로 사용하고, 메모이제이션도 하지 않고 짜본다.

 

주어진 값 n에 대해서, 1에서 n까지의 모든 수(n 포함)에 대해서 변환수(1까지 도달할 때까지 변화되는 회수)를 구하고, 이 중에서 가장 최대 변환수를 보이는 값이 결괏값이다.

 

여기서 n=1일 때는, 당연히 1이다. n보다 작거나 같은 값중에서 가장 최대변환수를 보이는 값을 찾는 것이기에, 1밖에 없으니 당연히 1

n=2의 경우는 {2, 1}로 변하기에 C(2)=2가되어 C(1)=1보다 커서, 답은 2가 된다.

따라서, n<=2 의 경우는 그대로 n을 리턴한다.

 

그다음은 i를 2..=n까지 증가시키면서 이제 만들게 될 get_chain_cnt 함수를 통해 변환수를 계산하고, 가장 큰 최댓값을 찾아낸다. 

fn answer(n: u32) -> u32{    
    if n <= 2 {return n;}
    let mut max:u64 = 0;
    let mut max_start:u32 = 0;
    for i in 2..=n {
        let chain_cnt = get_chain_cnt(i as u64);      
        if chain_cnt >= max {
            (max_start, max) = (i, chain_cnt);             
        }
    }
    return max_start;
}

 

 

주어진 수에 대해 변환수를 계산하는 get_chain_cnt 함수는 다음과 같다.

짝수이면 n/2, 홀수이면 3n+1을 하면서 1이 될 때까지 진행시키면 cnt를 세면 된다.

fn get_chain_cnt(mut n:u64) -> u64 {    
    let mut cnt:u64 = 1;
    while n > 1{
        if n & 1 == 0 { n /= 2; }
        else { n = 3*n + 1; }
        cnt += 1;
    }    
    return cnt;
}

 

이렇게 풀면 답은 맞으나 타임아웃이 발생한다. 코드 효율화가 필요하겠다.

#[test]
fn test(){    
    assert_eq!(1, answer(1));
    assert_eq!(2, answer(2));
    assert_eq!(3, answer(3));
    assert_eq!(3, answer(4));
    assert_eq!(3, answer(5));
    assert_eq!(6, answer(6));
    assert_eq!(7, answer(7));
    assert_eq!(7, answer(8));
    assert_eq!(9, answer(9));
    assert_eq!(9, answer(10));
    assert_eq!(9, answer(15));
    assert_eq!(18, answer(18));
    assert_eq!(19, answer(20));
    assert_eq!(2223, answer(2223)); 
    assert_eq!(837799, answer(1000000));
    assert_eq!(837799, answer(1000001));
}

#[cfg(test)]
fn answer(n: u32) -> u32{    
    if n <= 2 {return n;}
    let mut max:u64 = 0;
    let mut max_start:u32 = 0;
    for i in 2..=n {
        let chain_cnt = get_chain_cnt(i as u64);      
        if chain_cnt >= max {
            (max_start, max) = (i, chain_cnt);             
        }
    }
    return max_start;
} 

#[cfg(test)]
fn get_chain_cnt(mut n:u64) -> u64 {    
    let mut cnt:u64 = 1;
    while n > 1{
        if n & 1 == 0 { n /= 2; }
        else { n = 3*n + 1; }
        cnt += 1;
    }    
    return cnt;
}

 

풀이 2 

---

몇 가지 효율적인 방법을 추가할 수 있다.

1) n이 홀수일 때 3n+1을 하게 되면, 3n+1의 값은 무조건 짝수가 된다. 왜냐면 3에 홀수를 곱하면 홀수가되고 여기에 1을 더한 것이기에 짝수. 따라서 3n+1이 짝수이기에 그 다음 변환은 (3n+1)/2 가된다.

즉, n이 홀수의 경우는 그 다음수를 (3n+1)/2로 변환하고, count를 1이 아닌 2 증가시키면 됨

2) 메모이제이션 사용

 

1) 번처럼, n이 홀수의 경우 (3n+1)/2로 처리한다. 이 경우 미리 다다음수로 변환한 것이기에 cnt를 하나 더 증가시킨다. 

if n % 2 == 0 {n /= 2;}
else { n = (3*n + 1)/2;  cnt += 1; }
cnt += 1;

 

2) 번 메모이제이션은, 이미 구한 변환수 값을 배열에 저장해서, 이미 계산된 변환수 값이 있으면, 다시 계산하지 않고 배열에 저장해 둔 값을 이용하는 것이다.

 

계산된 변환수를 저장하는 것은 아래 코드처럼, get_chain_cnt2 함수에 의해 계산된 결괏값 chain_cnt를 arr[i]에 저장해 둔다.

let chain_cnt:u64 = get_chain_cnt2(i as u64, &arr);        
arr[i as usize] = chain_cnt;

 

사용할 때는 arr에 해당 값이 존재하는지를 확인해서 있으면 그 값을 사용한다.

 

아래 코드에서 해당 n값이 arr에 있는지를 조사하기에 앞서, n값이 array의 크기보다 작은지 조사하는 것에 유의.

배열의 크기는 문제에서 주어지는 N의 크기 정도로 할당할 것이고, 실제 변환을 하다 보면 N 크기보다 더 큰 변환이 이루어지기에, 조사하는 값이 배열 범위를 넘어설 수도 있기 때문이다. 

 

예를 들어, N=5의 경우 변환 수는 {5, 16, 8, 4, 2, 1}로, N=5이기에 배열 크기를 6으로 잡고 메모이제이션을 할 것이기에, 5 다음에 나오는 변환값 16에 대해서는 배열에서 처리할 수 없는 것이다.

fn get_chain_cnt2(mut n:u64, cntarr:&Vec<u64>) -> u64 {    
    let mut cnt:u64 = 0;

    while n > 1{
        if (n as usize) < cntarr.len() && cntarr[n as usize] > 0 {
            cnt += cntarr[n as usize];
            break;
        }  
        ...

 

이렇게 구현한 코드는, 

#[test]
fn test2(){    
    assert_eq!(1, answer2(1));
    assert_eq!(2, answer2(2));
    assert_eq!(3, answer2(3));
    assert_eq!(3, answer2(4));
    assert_eq!(3, answer2(5));
    assert_eq!(6, answer2(6));
    assert_eq!(7, answer2(7));
    assert_eq!(7, answer2(8));
    assert_eq!(9, answer2(9));

    assert_eq!(9, answer2(10));
    assert_eq!(9, answer2(15));
    assert_eq!(18, answer2(18));
    assert_eq!(19, answer2(20));
    assert_eq!(2223, answer2(2223));  
    assert_eq!(837799, answer2(1000000));
    assert_eq!(837799, answer2(1000001));
    assert_eq!(3732423, answer2(5000000));    
}

#[cfg(test)]
fn answer2(n: u64) -> u64{  
    if n <= 2 {return n;}  
    let mut max:u64 = 0;
    let mut max_start:u64 = 0;    
    
    let mut arr:Vec<u64> = vec![0; n as usize + 1];
    arr[1]=1;
    for i in 2..=n {    
        let chain_cnt:u64 = get_chain_cnt2(i as u64, &arr);        
        arr[i as usize] = chain_cnt;
               
        if chain_cnt >= max {
            (max_start, max) = (i, chain_cnt);              
        } 
    }
    return max_start;
} 

#[cfg(test)]
fn get_chain_cnt2(mut n:u64, cntarr:&Vec<u64>) -> u64 {    
    let mut cnt:u64 = 0;

    while n > 1{
        if (n as usize) < cntarr.len() && cntarr[n as usize] > 0 {
            cnt += cntarr[n as usize];
            break;
        }        

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

 

이 정도 코드면 어느 정도 효율적인 코드라 할 수 있겠다.

그러나, 이 코드 형태로 hackerrank에 도전하면, 타임 아웃이 나온다.

 

이 코드는 주어진 N에 대해서 새로 메모이제이션을 할 배열을 만들어서 사용하는 것인데, 모든 문제에 앞서서 메모이제이션 배열을 만들고, 주어진 N에서는 이미 만든 배열값으로 답을 내게 해야만 통과할 수 있다.

풀이 3에서 그러한 코드이다.

풀이 3

---

모든 문제에 앞서서 미리 답을 구해서 배열에 저장 후, 실제 문제에 대해서는 해당 배열값을 출력하는 방식이다.

 

답을 구해서 배열에 저장하는 함수는 다음과 같다.

여기서, 2의 지수승에 해당하는 {2,4,8,16,...}에 대해서는, 모두 짝수이고 n/2 씩 작아지기에, 실제 변환을 하지 않아도 몇 번 변환해서 1이 되는지 알 수 있다. 해서, 2의 지수승에 대해서는 미리 값을 집어넣어 수행시간을 단축시킨다.

fn get_cnt_arr4(n:usize) -> Vec<u64> {
    let mut arr:Vec<u64> = vec![0; n];

    //[2]=2, [4]=3, [8]=4, [16]=5, [32]=6
    arr[1] = 1;
    let mut i:usize = 2;
    let mut k = 2;
    while i < n {
        arr[i] = k;
        i *= 2;  k += 1;
    }

    for i in 3..n {
        arr[i] = count_chain4(i as u64, &arr);
    }

    //----------
    let mut ans:Vec<u64> = vec![0; n];
    let mut max:u64 = 1;
    let mut max_start:u64 = 1;
    // arr: {0,1,2,8,3,6,9,..}
    // ans: {0,1,2,3,3,3,6,...}
    for i in 1..n {
        if arr[i] >= max {
            max = arr[i];
            max_start = i as u64;
        }
        ans[i] = max_start;
    }
    return ans;
}

 

이렇게 문제가 주어지기 전에 미리 답을 구해뒀다가 사용하는 것이기에, 좀 그렇다. 그러나, 이렇게 하지 않으면 hackerrank 사이트 문제를 통과하지 못한다.

 

통과하는 코드는 아래와 같다.

use std::io::{self, BufRead};

fn main() {
    let stdin = io::stdin();
    let mut stdin_iterator = stdin.lock().lines();

    let t = stdin_iterator.next().unwrap().unwrap().trim().parse::<i32>().unwrap();
    
    let arr = get_cnt_arr(5000001);
    
    for i in 0..t {
        let n = stdin_iterator.next().unwrap().unwrap().trim().parse::<i32>().unwrap();
        println!("{}",answer4(n as u64, &arr));        
    }   
     
}

fn answer4(n: u64, arr:&Vec<u64>) -> u64{
    return arr[n as usize];
}

fn get_cnt_arr(n:usize) -> Vec<u64> {
    let mut arr:Vec<u64> = vec![0; n];

    //[2]=2, [4]=3, [8]=4, [16]=5, [32]=6
    arr[1] = 1;
    let mut i:usize = 2;
    let mut k = 2;
    while i < n {
        arr[i] = k;
        i *= 2;  k += 1;
    }

    for i in 3..n {
        arr[i] = count_chain4(i as u64, &arr);
    }

    //----------
    let mut ans:Vec<u64> = vec![0; n];
    let mut max:u64 = 1;
    let mut max_start:u64 = 1;
    // arr: {0,1,2,8,3,6,9,..}
    // ans: {0,1,2,3,3,3,6,...}
    for i in 1..n {
        if arr[i] >= max {
            max = arr[i];
            max_start = i as u64;
        }
        ans[i] = max_start;
    }
    return ans;
}

fn count_chain4(n:u64, arr:&Vec<u64>) -> u64{
    if (n as usize) < arr.len() && arr[n as usize] > 0 {
        return arr[n as usize];       
    }       

    let cnt:u64;
    if n%2 == 0 {
        cnt = 1 + count_chain4(n/2, arr);    
    }else {
        cnt = 2 + count_chain4((3*n+1)/2, arr);        
    }
    
    return cnt;
}

총평

---

메모이제이션과 관련된 문제이다. 

 

hackerrank에서는, 문제로 N이 주어질 때마다 각각 메모이제이션을 해서는 타임아웃이 발생한다. 좀 이상하다.

미리 배열을 만들고, 모든 문제에서 이 배열값을 이용하도록 해야만 통과가 된다. 

 

전체 소스코드

---

p14.rs 

#[test]
fn test(){    
    assert_eq!(1, answer(1));
    assert_eq!(2, answer(2));
    assert_eq!(3, answer(3));
    assert_eq!(3, answer(4));
    assert_eq!(3, answer(5));
    assert_eq!(6, answer(6));
    assert_eq!(7, answer(7));
    assert_eq!(7, answer(8));
    assert_eq!(9, answer(9));
    assert_eq!(9, answer(10));
    assert_eq!(9, answer(15));
    assert_eq!(18, answer(18));
    assert_eq!(19, answer(20));
    assert_eq!(2223, answer(2223)); 
    assert_eq!(837799, answer(1000000));
    assert_eq!(837799, answer(1000001));
}

#[cfg(test)]
fn answer(n: u32) -> u32{    
    if n <= 2 {return n;}
    let mut max:u64 = 0;
    let mut max_start:u32 = 0;
    for i in 2..=n {
        let chain_cnt = get_chain_cnt(i as u64);      
        if chain_cnt >= max {
            (max_start, max) = (i, chain_cnt);             
        }
    }
    return max_start;
} 

#[cfg(test)]
fn get_chain_cnt(mut n:u64) -> u64 {    
    let mut cnt:u64 = 1;
    while n > 1{
        if n & 1 == 0 { n /= 2; }
        else { n = 3*n + 1; }
        cnt += 1;
    }    
    return cnt;
}

//-------------------------------

// - n에 대해서,
//   짝수일때: n/2
//   홀수일때: 3n+1 -> 다시 짝수가 된다.
// - 따라서, Count를 구하는 함수를 C()라고하면, 
//   짝수일때는 C(n/2)을 호출, 홀수일때는 C((3n+1)/2)를 호출
#[test]
fn test1(){  
    assert_eq!(1, answer1(1));
    assert_eq!(2, answer1(2));
    assert_eq!(3, answer1(3));
    assert_eq!(3, answer1(4));
    assert_eq!(3, answer1(5));
    assert_eq!(6, answer1(6));
    assert_eq!(7, answer1(7));
    assert_eq!(7, answer1(8));
    assert_eq!(9, answer1(9));

    assert_eq!(9, answer1(10));
    assert_eq!(9, answer1(15));
    assert_eq!(18, answer1(18));
    assert_eq!(19, answer1(20));
    assert_eq!(2223, answer(2223)); 
    assert_eq!(837799, answer1(1000000));
    assert_eq!(837799, answer1(1000001));
}

#[cfg(test)]
fn answer1(n: u32) -> u32{    
    if n <= 2 {return n;}
    let mut max:u64 = 0;
    let mut max_start:u32 = 0;
    for i in 2..=n {
        let chain_cnt = get_chain_cnt1(i as u64);
        if chain_cnt >= max {
            (max_start, max) = (i, chain_cnt);              
        }
    }
    return max_start;
} 

#[cfg(test)]
fn get_chain_cnt1(mut n:u64) -> u64 {  
    let mut cnt:u64 = 1;

    while n > 1{
        if n & 1 == 0 {
            n /= 2;
        }else {            
            n = (3*n + 1)/2;
            cnt += 1;
        }
        cnt += 1;
    }    
    return cnt;
}

//-------------------------------
// - Hashmap이 아닌 큰 배열을 이용해서, 기존 C(t)값이 있는지 확인하게
//   --> 속도 빨라짐
// - 이 때, 배열크기는 limit. 그리고, 배열값을 읽을 때는 배열크기 체크해야함
#[test]
fn test2(){    
    assert_eq!(1, answer2(1));
    assert_eq!(2, answer2(2));
    assert_eq!(3, answer2(3));
    assert_eq!(3, answer2(4));
    assert_eq!(3, answer2(5));
    assert_eq!(6, answer2(6));
    assert_eq!(7, answer2(7));
    assert_eq!(7, answer2(8));
    assert_eq!(9, answer2(9));

    assert_eq!(9, answer2(10));
    assert_eq!(9, answer2(15));
    assert_eq!(18, answer2(18));
    assert_eq!(19, answer2(20));
    assert_eq!(2223, answer2(2223));  
    assert_eq!(837799, answer2(1000000));
    assert_eq!(837799, answer2(1000001));
    assert_eq!(3732423, answer2(5000000));    
}

#[cfg(test)]
fn answer2(n: u64) -> u64{  
    if n <= 2 {return n;}  
    let mut max:u64 = 0;
    let mut max_start:u64 = 0;    
    
    let mut arr:Vec<u64> = vec![0; n as usize + 1];
    arr[1]=1;
    for i in 2..=n {    
        let chain_cnt:u64 = get_chain_cnt2(i as u64, &arr);        
        arr[i as usize] = chain_cnt;
               
        if chain_cnt >= max {
            (max_start, max) = (i, chain_cnt);              
        } 
    }
    return max_start;
} 

#[cfg(test)]
fn get_chain_cnt2(mut n:u64, cntarr:&Vec<u64>) -> u64 {    
    let mut cnt:u64 = 0;

    while n > 1{
        if (n as usize) < cntarr.len() && cntarr[n as usize] > 0 {
            cnt += cntarr[n as usize];
            break;
        }        

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


//---------------------
// 2^i승에 해당하는 값을 미리 만들어서 사용. [2]=2, [4]=3, [8]=4, [16]=5, [32]=6
#[test]
fn test21(){    
    assert_eq!(1, answer21(1));
    assert_eq!(2, answer21(2));
    assert_eq!(3, answer21(3));
    assert_eq!(3, answer21(4));
    assert_eq!(3, answer21(5));
    assert_eq!(6, answer21(6));
    assert_eq!(7, answer21(7));
    assert_eq!(7, answer21(8));
    assert_eq!(9, answer21(9));

    assert_eq!(9, answer21(10));
    assert_eq!(9, answer21(15));
    assert_eq!(18, answer21(18));
    assert_eq!(19, answer21(20));
    assert_eq!(2223, answer21(2223));  
    assert_eq!(837799, answer21(1000000));
    assert_eq!(837799, answer21(1000001));
    assert_eq!(3732423, answer21(5000000));    
}

#[cfg(test)]
fn answer21(n: u64) -> u64{  
    if n <= 2 {return n;}  
    let mut max:u64 = 0;
    let mut max_start:u64 = 0;    
    
    let mut arr:Vec<u64> = vec![0; n as usize + 1];
    arr[1] = 1;
    let mut i:usize = 2;
    let mut k = 2;
    while i < n as usize {
        arr[i] = k;
        i *= 2;  k += 1;
    }
    
    for i in 2..=n {    
        let chain_cnt:u64 = get_chain_cnt21(i as u64, &arr);        
        arr[i as usize] = chain_cnt;
               
        if chain_cnt >= max {
            (max_start, max) = (i, chain_cnt);              
        } 
    }
    return max_start;
} 


#[cfg(test)]
fn get_chain_cnt21(mut n:u64, cntarr:&Vec<u64>) -> u64 {    
    let mut cnt:u64 = 0;

    while n > 1{
        if (n as usize) < cntarr.len() && cntarr[n as usize] > 0 {
            cnt += cntarr[n as usize];
            break;
        }        

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


//----------------------------
// 재귀호출 이용
#[test]
fn test3(){        
    assert_eq!(1, answer3(1));
    assert_eq!(2, answer3(2));
    assert_eq!(3, answer3(3));
    assert_eq!(3, answer3(4));
    assert_eq!(3, answer3(5));
    assert_eq!(6, answer3(6));
    assert_eq!(7, answer3(7));
    assert_eq!(7, answer3(8));
    assert_eq!(9, answer3(9));
    assert_eq!(9, answer3(10));
    assert_eq!(9, answer3(15));
    assert_eq!(18, answer3(18));
    assert_eq!(19, answer3(20));
    assert_eq!(2223, answer2(2223)); 
    assert_eq!(837799, answer3(1000000));
    assert_eq!(837799, answer3(1000001));
    assert_eq!(3732423, answer3(5000000));
}

#[cfg(test)]
fn answer3(n: u64) -> u64{
    if n <= 2 {return n;}  
    let mut max:u64 = 0;
    let mut max_start:u64 = 0;   
    let mut arr:Vec<u64> = vec![0; n as usize + 1];
    arr[1] = 1; arr[2] = 2;  

    let mut start:u64 = 1;
    if n % 2 == 0 {start = n/2;}
    for i in start..=n {
        let cnt = count_chain(i, &mut arr);
        if cnt >= max { 
            max_start = i; 
            max = cnt;
        }
    }

    return max_start;
}

#[cfg(test)]
fn count_chain(n:u64, mut arr:&mut Vec<u64>) -> u64{
    if (n as usize) < arr.len() && arr[n as usize] > 0 {
        return arr[n as usize];       
    }       

    let cnt:u64;
    if n%2 == 0 {
        cnt = 1 + count_chain(n/2, &mut arr);    
    }else {
        cnt = 2 + count_chain((3*n+1)/2, &mut arr);        
    }

    if (n as usize) < arr.len() {
        arr[n as usize] = cnt;
    }
    return cnt;
}

//---------------------------------
// 미리 만들어서 사용
#[test]
fn test4(){    
    let arr = get_cnt_arr4(5000001);

    assert_eq!(1, answer4(1, &arr));
    assert_eq!(2, answer4(2, &arr));
    assert_eq!(3, answer4(3, &arr));
    assert_eq!(3, answer4(4, &arr));
    assert_eq!(3, answer4(5, &arr));
    assert_eq!(6, answer4(6, &arr));
    assert_eq!(7, answer4(7, &arr));
    assert_eq!(7, answer4(8, &arr));
    assert_eq!(9, answer4(9, &arr));

    assert_eq!(9, answer4(10, &arr));
    assert_eq!(9, answer4(15, &arr));
    assert_eq!(18, answer4(18, &arr));
    assert_eq!(19, answer4(20, &arr));
    assert_eq!(837799, answer4(1000000, &arr));
    assert_eq!(837799, answer4(1000001, &arr));
    assert_eq!(3732423, answer4(5000000, &arr));    
}


#[cfg(test)]
fn answer4(n: u64, arr:&Vec<u64>) -> u64{
    return arr[n as usize];
}

#[cfg(test)]
fn get_cnt_arr4(n:usize) -> Vec<u64> {
    let mut arr:Vec<u64> = vec![0; n];

    //[2]=2, [4]=3, [8]=4, [16]=5, [32]=6
    arr[1] = 1;
    let mut i:usize = 2;
    let mut k = 2;
    while i < n {
        arr[i] = k;
        i *= 2;  k += 1;
    }

    for i in 3..n {
        arr[i] = count_chain4(i as u64, &arr);
    }

    //----------
    let mut ans:Vec<u64> = vec![0; n];
    let mut max:u64 = 1;
    let mut max_start:u64 = 1;
    // arr: {0,1,2,8,3,6,9,..}
    // ans: {0,1,2,3,3,3,6,...}
    for i in 1..n {
        if arr[i] >= max {
            max = arr[i];
            max_start = i as u64;
        }
        ans[i] = max_start;
    }
    return ans;
}

#[cfg(test)]
fn count_chain4(n:u64, arr:&Vec<u64>) -> u64{
    if (n as usize) < arr.len() && arr[n as usize] > 0 {
        return arr[n as usize];       
    }       

    let cnt:u64;
    if n%2 == 0 {
        cnt = 1 + count_chain4(n/2, arr);    
    }else {
        cnt = 2 + count_chain4((3*n+1)/2, arr);        
    }
    
    return cnt;
}

 

끝