[ SWEA 6782 ] 현주가 좋아하는 제곱근 놀이 (C++)

SWExpertAcademy의 현주가 좋아하는 제곱근 놀이(6782 / D5) 문제이다.

[ 문제풀이 ]

1) 먼저 N 값이 주어졌을 때, 어떻게 해야 2로 갈 수 있는지부터 생각을 한번 해보자.

   N의 범위는 2보다는 크거나 같은 값들이 들어오게 된다.

   그리고 우리는 이 N값을 + 1 을 시키거나 루트를 씌워서 N값을 바꿀 수가 있다.

   그렇다면, N이 2보다 더 큰 값이 들어왔을 때, N을 2로 만들기 위해서는 루트를 씌우는 방법 밖에 없다.

   왜냐하면 N이 2보다 더 큰데 + 1 로는 절대 2를 만들 수 없기 때문이다.

   그래서 본인은 현재 숫자가 루트가 씌워지는(루트를 씌웠을 때 정수가 나온다면) 숫자라면 N값을 루트N 으로 바꿔주었고,

   그게 아니라면, 그 다음 거듭제곱의 숫자까지 바꾼 횟수를 더해 주었다.

   예를 들어 N = 5 인 경우를 통해 알아보자.

   루트를 씌워보니, 딱 떨어지는 정수가 나오지 않는 숫자이다.

   그렇다면, N 을 + 1을 시켜보고, 또 루트를 씌워보는 것이 아니라, N을 9로 만들어버리고 4번 바꿨습니다 라고 해버리는

   것이다.

   더욱 구체적으로 이야기를 해보면, N = 5일 때, 루트를 씌우게 되면 2.xxx가 나오게 될 것이다.

   하지만, 단순 long long 형으로 ll Temp = 루트(5) 를 하게 되면, Temp에는 '2'가 저장될 것이다. 소수점까지 저장이

   되지 않는다. 그럼 체크를 한번 해보는 것이다. Temp * Temp == 5 인지 ! 5가 나오지 않을 것이다. 그렇다면,

   이 숫자는 루트를 씌울 수 없는 숫자라는 것을 뜻한다.

   그럼, 여기서 '6', '7', '8'을 일일이 하나하나 확인할 필요가 있냐라는 것이다.

   어차피 N이 2보다 큰 값이기 때문에, 절대로 N + 1을 하는 중간과정에서 '2'가 나올리는 없다.

   따라서, 바로 그 다음 제곱근인 '9'로 가는 것이다. 그럼 이 '9'는 어디서 나온 숫자냐 ?

   아까 위에서 구할 때, Temp = 2 였다. 그런데, 2 x 2 = 5 가 아니므로, "현재 N은 2의 거듭제곱보다는 큰 숫자이구나" 라는

   것을 알 수 있다. 즉, 2에서 + 1을 한 '3 x 3'이 "그 다음 제곱근 숫자" 라는 것을 알 수 있다.

   5를 9로 바꾸기 위해서는 + 1을 총 4번 해줘야 한다. 그럼, 여기서 바꾼 횟수를 + 4를 해버리는 것이다.

   이 중간과정인 5에서 + 1을 한 '6'을 체크해보고, +1을 한 '7'을 체크해보고, +1을한 '8'을 체크할 필요가 없다는 것이다.

   그리고, 제곱근이 가면 갈수록 숫자가 커지고, N 값의 범위가 10^12 이하이기 때문에 굉장히 큰 숫자가 들어올 수도

   있다.

   코드는 되게 간단한데, 말로 풀어서 설명하자니 오히려 더 복잡해진 것 같다...

 

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<cmath>
 
#define endl "\n"
typedef long long ll;
using namespace std;
 
ll N, Answer;
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    int Cnt = 0;
    while (N > 2)
    {
        /* 먼저, N에 루트를 씌워본다. */
        ll Res = (ll)sqrt(N);
        if (Res * Res == N)
        {
            /*  N이 루트를 씌워도 되는 숫자일 때 */
            N = Res;
            Cnt++;
            /* 루트를 씌우고, Cnt++ */
        }
        else
        {
            /* 루트를 씌울 수 없는 숫자일 때 */
            Cnt = Cnt + pow(Res + 1, 2) - N;
            N = pow(Res + 1, 2);
            /* 그 다음 거듭제곱한 숫자로 바로 넘어가버린다. */
            /* 또한, 횟수도 현재 숫자에서 그 다음 거듭제곱한 숫자로
             * 바꾸는데 걸리는 횟수.(+1을 몇번 하는지)
            */
        }
    }
    Answer = Cnt;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        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;
}