[프로그래머스] 콜라츠 추측

 

 

문제

소스코드

constexpr int LIMIT_CYCLE = 500;
 
//Collaztz conjecture
int solution(int num) {
    int answer = -1;
    long long llnum = num;
 
    if (llnum == 1)
        return 0;
 
    for (int i = 0; i < LIMIT_CYCLE; ++i) {
 
        //1-1 입력된 수가 짝수라면 2로 나눈다.
        if (llnum % 2 == 0) {
            llnum /= 2;
        }
        //1-2 입력된 수가 홀수라면 3을 곱하고 1을 더한다.
        else {
            llnum = llnum * 3 + 1;
        }
        //2 결과로 나온 수에 같은 작업을 1이 될 때 까지 반복(500)
        if (llnum == 1) {
            answer = i+1;
            break;
        }
    }
 
    return answer;
}

 

 

후기

 

이 문제를 해결하기 위한 키워드는 콜라츠 추측이다.

 

 콜라츠 추측(Collatz conjecture)은 1937년에  처음으로 이 추측을 제기한 로타르 콜라츠의 이름을 딴 것으로 3n+1 추측,

울람 추측, 혹은 헤일스톤(우박) 수열 등 여러 이름으로 불린다. 

 

이 문제는 주어진 법칙만 알고있으면 푸는데 어려운 문제는 아니다. 단순한 문제를 풀고 싶을 때에는 괜찮다고 생각한다.

 

출처 및 레퍼런스

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/12943