[프로그래머스 2단계] 알고리즘 18. 콜라츠 추측

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 18. 콜라츠 추측

1937년 Collatz란 사람에 의해 제기된 이 추측은, 입력된 수가 짝수라면 2로 나누고, 홀수라면 3을 곱하고 1을 더한 다음, 결과로 나온 수에 같은 작업을 1이 될 때까지 반복할 경우 모든 수가 1이 된다는 추측입니다. 예를 들어, 입력된 수가 6이라면 6→3→10→5→16→8→4→2→1 이 되어 총 8번 만에 1이 됩니다. collatz 함수를 만들어 입력된 수가 몇 번 만에 1이 되는지 반환해 주세요. 단, 500번을 반복해도 1이 되지 않는다면 –1을 반환해 주세요.

#include<iostream>

using namespace std;

int collatz(int num)

{

    int answer = 0;

    return answer;

}

int main()

{

    int testCase = 6;

    int testAnswer = collatz(testCase);

    cout<<testAnswer;

}

풀이 : 

이 문제의 핵심은 간단하다. 500번을 반복해서 그 수가 짝수일 때는 2로 나누고 홀 수 일때는 3을 곱해준 후 1을 더해주면 된다. 만약 결과가 1이면 그 반복한 횟수를 반환해주고 500번을 돌아도 1이 안나오면 -1을 반환해주면 된다. 내가 짠 코드는 다음과 같다.

int collatz(int num)

{

long long ans = num;

    for(int i=0; i<500; i++)

{

if (ans == 1)

    return i;

ans = (ans % 2 == 0) ? (ans / 2) : (3 * ans + 1);

}

    return -1;

}

왜 long long 타입으로 형 변환을 해주었냐면 int로 했을 때 자꾸 에러가 났다. 한 번 cout을 해보았는데(프로그래머스 알고리즘 연습은 다행히 결과를 나타내주었다.) int형의 범위를 넘어선 숫자 입력이 들어가는 것을 확인할 수 있었다. 혹시나 로직이 잘못 됐나 하는 마음에 BigInteger와 같이 큰 숫자형을 지원하는 자바나 파이썬으로 확인해 보았는데 아무 문제 없이 동작하였다. 에러의 원인은 로직은 맞는데 자료형의 크기가 턱 없이 부족함이 문제였다는 것을 알 수 있었다. 이 후 long long 타입으로 형 변환하니까 정답을 출력해주었다. 허허 다른 사람들 중에는 그냥 int로 해도 되던데 왜 내껀 깐깐하지...