8993. 하지 추측 D4

 

다른 글 작성하다가 현타와서.. 알고리즘 문제를 하나 풀었다. 

일단 문제는 

 

다음과 같은 프로그램을 생각해 보자.

while (N > 1){

       if (N mod 2 == 0) N := N / 2

        else N := 3 * N + 1

}

이 문제는 유명한 “콜라츠 추측” 문제로, 모든 자연수 N에 대해서 이 프로그램이 종료하는 것 (즉, 무한 루프에 빠지지 않는 것)이 추측되지만, 아직 증명되지는 않았다.

콜라츠 추측에 영감을 받은 하지는, “하지 추측”을 만들었다. 하지 추측은 모든 자연수 N에 대해서 다음 프로그램이 종료한다는 추측이다.

 while (N > 1){

        if (N mod 2 == 0) N := N / 2

        else N := 3 * N + 3

}

과연 하지의 추측은 옳을까? 자연수 N이 주어졌을 때, N에 대해서 이 프로그램이 종료하는지 판별하라.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

두 번째 줄부터 각 테스트 케이스에서의 정수 N이 주어진다. (1 ≤ N ≤ 1014)  
  

[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,
프로그램이 종료되면 “YES”, 종료되지 않고 무한히 반복된다면 “NO”를 출력한다.

 

 

문제는 이렇다. '콜라츠 추측'이라는 것을 보고 영감을 받아 문제를 만들었다는데 난 뭔지 모른다.

어차피 메인은 하지 추측의 while이니까 이것을 분석해 보기로 했다.

예제는 3,4를 집어 넣고 No, Yes 를 출력하는데 예제 코드를 그대로 넣고 3을 입력하면 멈춰버려서

for(int i=0;i<10&&N>1;i++){

을 while대신에 넣어서 10번만 돌려보았다. for문만 다돌면 true가 return된다.

그랬더니

되는 것과 안되는 것 비교

1번은 원래 "NO"가 나와야 한다. for문이라 "YES"나온거다.

이렇게 결과가 나왔다. 첫 번째 케이스는 계속 특정한 패턴이 반복되는 것을 찾아냈다.

두 번째 케이스는 깔끔하게 두번만 돌고 true가 return 되었다.

첫 번째 케이스의 패턴을 보고 특정 숫자가 두 번이상 반복이 되면 루프에 빠져 나오지 못하겠다고 생각을 했다.

그래서 queue를 이용해 front와 다르면 집어 넣고 같으면 false를 return하면 되겠다고 생각했고 

조금은 맞을 것 같아서 몇 개나 맞으려나 하고 돌려봤는데

 

패스했다... D4치고는 10분컷이라 살짝 당황했다.. 예외 상황이 없었나 보다..

 

여기 내가 푼 코드다

정답 낸 사람들을 보니 나보다 훨씬 짧게 짠 사람도 많다. 다른 방법이 여러가지 있나보다

#include <iostream>
#include <queue>
using namespace std;
bool solve(long long N)
{
    queue<long long>ARR;
    while(N>1){
    //for(int i=0;i<10&&N>1;i++){
        if(N%2==0)
            N=N/2;
        else{
            ARR.push(N);
            if(N==ARR.front())
                return false;
            N=3*N+3;
        }
 
    }
    return true;
}
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int TC;
    long long N;
    cin>>TC;
    for (int t=1;t<=TC;t++)
    {
        cin>>N;
        if(solve(N))
            cout<<"#"<<t<<' '<<"YES"<<'\n';
        else
            cout<<"#"<<t<<' '<<"NO"<<'\n';
    }
    return 0;
}