6782. 현주가 좋아하는 제곱근 놀이

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWgqsAlKr9sDFAW0&categoryId=AWgqsAlKr9sDFAW0&categoryType=CODE

SW Expert Academy

10000개 테스트케이스를 합쳐서 C의 경우 1초 / C++의 경우 1초 / Java의 경우 2초

 

10000개 테케에 N범위도 10^12이므로 DFS,  BFS 완탐으로 불가능

while 반복으로 푸는것도 문제가 있음.

 

제곱근이 가능하면 제곱근 시키고 아니면 ++시키는 간단한 로직으로는 많은 반복이 생기므로

제곱근이 아닌경우 한번씩 ++ 시키는 것이 아니라 제곱근이 되도록 한번에 더해서 만들어야함.

제곱근이 되려면 현재 N을 sqrt시킨것의 + 1 의 제곱이 N이 되어야 함 

(현재 sqrt(N) 이 1.xxxxx라면 sqrt(N)이 2가 되는 것이 목적이므로 )

그래서 그 차이만큼 횟수에 더해주고 제곱근 취해주는 과정을 더해주고 N을 변경.

 

1인경우는 예외케이스로 무한 루프에 빠지므로 1에대한 처리 해줘야함. 1은 제곱근 가능해서 계속 제곱근 호출함.

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



long long N, result;
bool check(long long n)
{
	long double temp = sqrt(n);
	long long temp1 = sqrt(n);

	if (temp - temp1 == 0)
	{
		return true;
	}

	return false;
}

int main(void)
{
	int test_case;
	int T;

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
		result = 0;

		while (N != 2)
		{
			if (N == 1)
			{
				N++;
				result++;
				break;
			}
			
			if (check(N))
			{
				N = sqrt(N);
				result++;
			}
			else
			{
				result += pow((long long)sqrt(N)+1,2) - N;
				N = sqrt(N) + 1;
				result++;

			}
		}

		cout << "#" << test_case << " " << result << endl;

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.

}