Problem 14 : Longest Collatz sequence (5%)

Description

original

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

n → n/2 (n is even) n → 3n + 1 (n is odd)

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

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 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.

간략해석

양의 정수에서 짝수면 /2, 홀수면 * 3+1을 해서 1까지 도달하게 만드는 과정이 있습니다. 100만 이하의 수 중에서 이 과정이 가장 긴 수는 무엇입니까.

Idea & Algorithm

naive idea

간단한 구현으로 함수를 만들어 구현하면 된다.

advanced idea

하지만 모든 수를 구현하기에는 반복되는 연산이 많으므로, 메모이제이션을 통해 연산을 줄일 수 있다. DP를 사용하면 된다.

단, 수가 얼마나 커질지는 모르니 그 부분에 대해서는 예외처리하고 해결하는 것이 좋다. 하지만 더 정확하게 하기 위해서는 map을 이용하여 범위를 모르는 부분을 저장하고, 아닌 부분은 array에 저장하여 접근 속도를 빠르게 한다.

재귀 DP의 일종으로 레퍼런스 변수 사용시 편하다.

source code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e6;

int dp[MAXN+5];
map<ll, int> dp2;

int f(ll ith){
    int &ret = ith > MAXN ? dp2[ith] : dp[ith];
    if(ret) return ret;
    if(ith&1) return ret = f(ith*3+1)+1;
    return ret = f(ith/2)+1;
}

int main(){
    dp[1] = 1;
    int mi = 0;
    for(ll i = 2 ; i <= MAXN ; i++){
        dp[i] = f(i);
        if(dp[i] > dp[mi]){
            mi = i;
        }
    }
    cout << mi << endl;
    cout << dp[mi] << endl;
}

Problem 014