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

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AWgqsAlKr9sDFAW0

< 입력 >

정수 N (1<=N<=10^12)

< 출력 >

N을 2로 바꾸는데 필요한 횟수

< 풀이 >

D5라서 겁먹고 시작했는데 단순한 문제였다.

문제가 어렵다기 보다는 테스트 케이스가 10,000개에 수의 범위가 10^12기 때문에

어떤 방법으로 시간을 줄여서 풀 것인지가 중요한 문제이다.

따로 줄이는 과정을 생각해보지도 않았고 while문 돌렸는데 풀려서.. 다른 사람들이 어떤 방법으로

시도를 했고 시간초과로 고민을 하는지는 잘 모르겠다.

-----------------------------------------------------------------------------------------------------------------------

아마도 "더 많이 더한 후에 제곱근을 하면 더 좋은 경우가 나올 수 있지 않을까?"라는 생각으로 다양한 방법을 생각해본 것이 오히려 틀린 이유라고 생각한다.

이 문제는 가장 가까운 제곱수를 찾는 것이 핵심이다.

제곱을 한 값이 커질수록 제곱수와 제곱수 사이의 간격이 커지기 때문에 오히려 더해서 다음 제곱수를 찾는 과정에서 더 많은 조작이 필요한 것이 자명한 사실이기 때문이다.

-----------------------------------------------------------------------------------------------------------------------

먼저, 숫자 N을 조작할 수 있는 방법은 2가지이다.

1. N에 1을 더한다.

2. N의 제곱근이 정수일 경우 N에 제곱근을 씌운다.

이 조건을 통해 알 수 있는 점은 N은 1번 조작에 의해서만 증가하고 2번 조작에 의해서만 감소한다는 점이다.

그러므로 N이 1인 경우를 제외하면 N을 제곱근이 정수일때까지 더하고 제곱근을 씌워주면 된다.

수를 바꿀 수 있는 여러가지 방법이 존재하지 않다는 점에서 단순하게 느껴진 문제였다.

사용한 방법은 while문의 시작에서 N에 제곱근을 씌운 값을 다시 제곱을 한다.

제곱근을 씌울 때 (long long)을 씌우게 되면 n보다 작거나 같은 제곱수들 중 최대값을 구할 수 있다.

그렇게 구한 값에 -N을 한 결과를 temp라는 변수에 넣는다.

이 때, temp가 0이라면 N이 제곱수라는 뜻이므로 제곱근을 씌우고 횟수에 1을 더한다.

 그 외의 경우는 N이 제곱수가 아니라는 뜻이므로

(long long)sqrt(N) +1 을 제곱한 수가 될 때까지 더해야한다.

그 차이만큼 횟수에 더하고 제곱수가 되었으므로 제곱근을 씌우기 위한 1번의 횟수를 더 더한다.

이러면 .. 끝 !

---

- 소스 코드 -

#include<iostream>
#include<math.h>
 
using namespace std;
 
typedef long long ll;
 
int main(void){
    int T;
    cin>>T;
    for(int test_case=1;test_case<=T;test_case++){
        // n이 10^12까지므로 long long으로 받기
        ll n;
        scanf("%lld",&n);
        ll result=0;
        while(n!=2){
            // n이 1일 경우를 예외처리 해주지 않으면 무한루프
            if(n==1){
                result++;
                break;
            }
            // n이 제곱수인지 따지는 식
            ll temp=0ll+pow((ll)sqrt(n),2)-n;
 
            // 만약 0이라면 제곱수이므로 루트를 씌운다.
            if(temp==0){
                n=(ll)sqrt(n);
                result+=1;
            }else{
            // 0이 아니라면 제곱수가 될때까지 1씩 증가시켜줘야 한다.
            // 그래서 sqrt(n)+1의 제곱과의 차이만큼 1씩 증가시키고
            // 제곱근 씌우는 횟수 1번을 더한다.
                result+=pow((ll)sqrt(n)+1,2)-n;
                result+=1;
                n=sqrt(n)+1;
            }
            
        }
        // lld 출력하면 끝 !
        printf("#%d %lld\n",test_case,result);
    }
}

---