SW academy 8993. 하지 추측

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

 

무한 반복이라면 중복해서 접근하는 수가 반드시 존재 할 것이고 그래서 나는 방문하지 않는 수는 map에 저장하고 

방문한 수인 경우 false를 리턴하는 로직을 짰는데 정답 29개가 최대였다...

어떤 테스트 케이스에서 틀리는지 모르겠음..

 

다만 N이 2로 나누어지는 것이 아니면 기존에는 3*N+3의 연산을 시켜주는 것인데

이를 보면 결국 N = 3(N+1)이므로 3의 배수 형태로 바뀌게 됨을 알 수 있다.

3의 배수는 짝수 형태든 홀 수 형태든 2로 나뉘었을 때 , 결국은 나머지를 갖게 되므로 다시 발산하는 형태의 연산으로 

무한 반복 된다 . 따라서 2로 나뉘었을 때, 나머지가 존재했다면 3의 배수 연산이 실행 될 것이고 이는 발산으로 이어지므로 그냥 바로 false 리턴하면 된다. 

 

 

 

#include<iostream>
#include<map>
using namespace std;

map<long long ,bool> m;

bool solve(long long N)
{
	while (N > 1){
		
		
        if(N % 2 == 0)
		{
			N = N / 2;
		}
        else
		{
			return false;
		} 
	}
	
	return true;
}


int main(void)
{
	int tc;
	cin >> tc;
	
	
	for(int i = 1; i <= tc; i++)
	{
		long long N;
		cin >> N;
		m.clear();
		if(solve(N))
		{
			cout <<"#"<<i<<" "<<"YES" << endl;
		}
		else
		{
			cout <<"#"<<i<<" "<< "NO" << endl;
		}
	}
	
	return 0;
	
}