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

programmers.co.kr/learn/courses/30/lessons/12943

코딩테스트 연습 - 콜라츠 추측

 

1. 서론

 

문제 자체는 쉬운데 함정이 있다. 난 생각해내지 못하고 질문하기에서 힌트를 봐버렸지만....

 

2. 문제 풀이

 

콜라츠란 사람이 한 추측이 있다.

 

1-1. 입력된 수가 짝수라면 2로 나눕니다.

1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.

2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.

 

이런 규칙이 있고, 만약 이 작업이 500 이상 반복되는 경우에는 멈추고 -1을 return 하고 아닌 경우에는 작업이 반복된 횟수를 return 한다.

 

나는 저 규칙대로 코드를 짰는데 자꾸 626331이 원래는 500이 넘어야 하는데 488이 나왔다. 질문하기에 가보니 나와 같은 사람이 꽤 여럿 있었는데 이건 C++인 경우에만 해당되는 문제였다. 3을 곱하는 과정에서 숫자가 커서 int형을 넘어가게 되는데 주어진 자료형이 int라서 그냥 별생각 없이 자료형은 바꾸지 않고 사용했는데 질문하기에서 int를 long으로 고쳐보라해서 그렇게 해봤더니 문제가 풀렸다.

 

3. 코드 설명

 

#include <string>
#include <vector>

using namespace std;

int solution(int num) {
    int answer = 0;
    long n = num;
    
    while(1)
    {
        if (n == 1) break;
        
        if (n % 2 == 0)
            n /= 2;
        else
            n = (n * 3) + 1;
        
        answer++;
              
        if (answer == 500) 
        {
            answer = -1;
            break;
        }    
    }
    
    return answer;
}

 

작업이 몇 번 진행될지는 미지수이기 때문에 while(1)로 무한으로 돌렸다.

1일 때까지 반복해야 하기 때문에 1인 경우엔 바로 멈춰준다.

그리고 그 밑으로 짝수일 경우, 홀수일 경우에 맞춰 식을 짜주고 작업을 몇 번 반복하는지 count 한다.

만약 작업이 500번째 이루어지는 경우에는 -1로 값을 주고 반복문을 멈춘다.