[ SWEA 8993 ] 하지 추측 (C++)

SWExpertAcademy의 하지추측(8993 / D4) 문제이다.

[ 문제풀이 ]

어떤 경우에 프로그램이 종료되는지 간단한 예시 몇 개를 통해서 한번 규칙을 찾아보자.

N = 3 일 경우를 한번 보자. 규칙에 맞게 N의 값을 변경해보면 다음과 같이 변할 것이다.

3 → 12 → 6 → 3 → 12 → 6  → ... 이 숫자들이 반복될 것이다.

따라서 3은 절대로 프로그램이 종료되지 않는다는 것을 알 수 있다.

N = 4 일 경우를 한번 보자.

4 → 2 → 1 로 프로그램이 종료된다.

N = 5 일 경우를 한번 보자.

5 → 18 → 9 → 30 → 15 → 48 → 24 → 12 → 6 → 3 → 12 → 6 ...

N = 8 일 경우를 한번 보자.

8 → 4 → 2 → 1

프로그램이 종료되지 않는다는 것을 알 수 있다.

여기서 한 가지 규칙을 찾아보면, "프로그램이 종료되는 N 값은 중복되는 숫자들이 발생하지 않는다" 라는 것이다.

반면, 프로그램이 종료되지 않는 N값들을 보게 되면 몇몇 숫자들이 "중복"해서 여러번 발생하게 된다.

즉 ! 규칙에 맞게 N값을 바꿔가면서 방문 체크를 해주면 된다. 기존에 이미 방문한 숫자가 다시 발생하게 된다면, 해당 N 값은

프로그램이 종료되지 않는 N값이라 판단할 수 있다.

단순 1차원 Visit배열을 통해서 값을 판단하기에는 숫자가 너무 커서 set을 이용해서 판단해 주었다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<set>
 
#define endl "\n"
typedef unsigned long long ll;
using namespace std;
 
ll N;
string Answer;
set<ll> Visit;
 
void Initialize()
{
    Visit.clear();
}
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    Visit.insert(N);
    while (N > 1)
    {
        if (N % 2 == 0)
        {
            N = N / 2;
            if (Visit.find(N) == Visit.end()) Visit.insert(N);
            else
            {
                Answer = "NO";
                return;
            }
        }
        else
        {
            N = (N * 3) + 3;
            if (Visit.find(N) == Visit.end()) Visit.insert(N);
            else
            {
                Answer = "NO";
                return;
            }
        }
    }
    Answer = "YES";
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}