[SW Experts Academy] 6782. 현주가 좋아하는 제곱근 놀이-(Java)

<서론>

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

SW Expert Academy

스터디 중 D4 말고 D5를 도전해봤다. D5 중에서 가장 많은 사람이 제출한 문제인 이번 문제를 풀어보았다. D4만 풀었다가 난이도를 하나 올려봤는데, 이번 문제는 어렵지 않은 문제였던 것 같다. 매일 알고리즘 한 문제 이상은 풀려고 하고, 한 문제 이상은 포스팅하려고 하는데.. 문제를 푸는 것보다 포스팅이 더 어려운 것 같다.

아무튼! 오늘도 풀어봅니다.

---

 

 

<본론>

이 문제는 입력 값이 10^12 까지라서 int 형태로는 입력을 받을 수 없다. 따라서 long 형태를 사용했다. 이 문제에서 핵심은 가장 가까운 제곱근을 구하는 것인데, Math 클래스를 사용하면 쉽게 가까운 제곱근을 구할 수 있다. 처음에는 Math 클래스의 sqrt 메소드 말고 for문을 이용해서 풀려고 했지만, 시간 초과가 나서 포기. 결국 Math 클래스를 사용했다. 입력값에 따라 범위를 나눠서 풀었다면 시간초과는 해결했으려나..

아무튼 이 문제는 제곱근만 구하면 되는 문제라 다른 설명은 모두 결론에 넣겠다.

---

 

 

<결론>

요약

1. 이 문제의 핵심은 가장 가까운 제곱수 찾기(큰 수들 중)

 1.1 +1은 값이 커지는 것

 1.2 제곱근은 값이 작아지는 것.

 1.3 제곱근할 수 있으면 무조건 제곱근하기

2. N의 제곱근을 구하고 정수로 파싱

3. 파싱한 값을 다시 제곱했을 때, N과 같은 지 비교

 3.1 N과 같다면 N을 제곱근한 값으로 N값 변경

 3.2 같지 않다면 N을 (루트(N) + 1 ) 로 N값 변경( 이때 (루트N +1)^2 에서 N의 차이만큼 카운트(ans) 증가)

4. 카운트 1 증가

5. 2가 될때까지 반복

import java.util.Scanner;
 
public class Solution {
 
    public static void main(String[] args) {
         
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int test_case=1; test_case<=T; test_case++) {
            long ans = 0;
            long n = Long.parseLong(sc.next());
            while(true) {
                if(n==2) break;
                long tmp = (long) Math.sqrt(n);
                if(tmp*tmp == n) {
                    n = tmp;
                } else {
                    ans += (tmp+1)*(tmp+1) - n;
                    n = tmp+1;
                }
                ans++;
            }
            System.out.println("#"+test_case+" "+ans);
        }
        sc.close();
    }
     
}