[2024.12.24] 콜라츠 추측

문제 설명

1937년 Collats란 사람에 의해 제기도니 이 추측은, 주어진 수가 1이 될 때가지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.

예를들어 주어진 수가 6이라면 6->3->10->5->16->8->4->2->1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야 하는지 반환하는 함수, solution을 완성해 주세요. 단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 -1을 반환해 주세요.

 

 

제한사항

• 입력된 수, num은 1이상, 8,000,000 미만인 정수입니다.

 

 

입출력 예

n			result	설명
6			8	문제의 설명과 같습니다.
16			4	16->8->4->2->1 이 되어 총 4번 만에 1이 됩니다.
626331			-1	626331은 500번을 시도해도 1이 되지 못하므로 -1을 리턴해야 합니다.

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>

#include <iostream>
using namespace std;

int solution(int num) {
    int answer = 0;
    long number=num;
    
    // 처음부터 1이 들어왔을 때
    if(number==1)
        return 0;
    
    // 1이 나올 때 까지 && 500번까지만 돌리기
    while((number!=1)&&(answer<500))
    {
        // 짝수나 홀수일 경우 작업
        if(number%2==0)
        {
            number=number/2;
        }
        else
        {
            number=number*3+1;
        }
        
        // 실행 횟수 업데이트
        answer++;
    }
    
    // 반환
    if(answer==500) // 500번 반복했는데 1이 안나왔을 때
    {
        return -1;
    }
    else // 500번 전에 1이 나왔을 때
    {
        return answer;
    }
}

이 경우에는 for반복문보다는 while 반복문을 쓰는 것이 더 유리하다. 횟수가 정해지지 않은 반복이 들어가야하기 때문이다.

 

제일 처음 1이 들어왔을 때부터 빠르게 빼준다. 1이 들어온 걸 확인하자마자 0을 반환해준다.

 

이제 1이 아닌 수가 들어왔을 경우를 처리해주어야 한다. while문을 이용하여 1이 아닐 동안, 그리고 500번이 안채워졌을 동안에는 계속 반복하도록 해준다. 그 안에서는 number에 따라 짝수인 경우와 홀수인 경우를 각각 구현해준다. 마지막으로 answer을 업데이트하여 실행된 횟수를 저장한다.

 

반복문을 돌다가 number이 1이 되거나 500번 돌았는데도 아직 number이 1이 아닐 때는 반복문을 나오도록 한다. 나와서 만약 answer이 500이라면 500번 반복해도 number을 1로 못 만들었다는 뜻이므로 -1을 리턴하고 그게 아닌 경우에는 answer를 리턴하도록 한다.

 

num을 굳이 long number로 옮겨서 사용한 이유는 아래서 설명하겠다.

 

 

오답 노트

num 매개변수를 그대로 사용해보려고 하였는데 이상하게 마지막 입출력 예에서만 626331이 488번만에 1이 된다는 다른 결과가 나왔다. 이 오류의 이유는 오버플로우 때문이다. 626331을 반복문 안에서 조작하다보면 int형에 담을 수 있는 수를 넘어선다. 짝수, 홀수일 때의 작업을 수행 후 num의 값을 계속 출력해보았다. 입출력 예3에서 488개의 로그를 확인하다보면 갑자기 음수가 등장하는 것을 볼 수 있다. 음수가 나오는 계산은 한적이 없는데 말이다.

C++에서 오버플로우를 처리하는 방식은 음수로 넘어가는 것이다. 예를 들어 short는 -32768~32767 까지 숫자를 사용할 수 있다. 만약 내가 short 타입으로 선언한 변수에 32767로 초기화를 하고 거기에 +1을 하면 32768은 범위에서 벗어나게 된다. 이 때 C++이 하는 행동은 내 short 타입 변수의 값을 최솟값으로 만들어버리는 것이다. 확인하면 -32768이 되어 있다.

 

그런 이유로 num을 그대로 사용하지 못하고 num을 long 타입의 number라는 변수에 다시 넣어 사용해 주었다.

 

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12943

프로그래머스