[코딩테스트] SWEA 6782 현주가 좋아하는 제곱근 놀이(Java)

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 6782 현주가 좋아하는 제곱근 놀이입니다.

포인트

해당 문제의 가장 포인트는 Math.sqrt()의 반환값입니다.

먼저 자바의 Math.sqrt() 스펙을 살펴보겠습니다.

/**
 * Returns the correctly rounded positive square root of a
 * {@code double} value.
 * Special cases:
 * <ul><li>If the argument is NaN or less than zero, then the result
 * is NaN.
 * <li>If the argument is positive infinity, then the result is positive
 * infinity.
 * <li>If the argument is positive zero or negative zero, then the
 * result is the same as the argument.</ul>
 * Otherwise, the result is the {@code double} value closest to
 * the true mathematical square root of the argument value.
 *
 * @param   a   a value.
 * @return  the positive square root of {@code a}.
 */
@IntrinsicCandidate
public static native double sqrt(double a);

스펙을 살펴보면 반올림된 양의 제곱근을 반환한다고 되어 있습니다.

예를 들어서 Math.sqrt(9) = 3이지만, Math.sqrt(8) = 2.xx 값으로 나오는 것입니다.

※ 추가로

• @IntrinsicCandidate 어노테이션은 JVM HotSpot 컴파일러가 이 메서드를 자동 최적화할 수 있도록 힌트를 주는 표시입니다.
  • 목적은 자바 바이트코드를 native CPU 명령어로 치환하기 위함입니다.(CPU 수준의 명령어로 대체해서 실행)
  • 사용 이유는 빠른 처리를 위한 함수들(Math.log10() 등)에 사용됩니다.
• native 키워드는 자바가 아닌 다른 언어(C/C++ 등..)으로 작성된 것을 나타내는 키워드입니다.
  • Math.sqrt()는 성능이 매우 중요한 함수이기 때문에,
    Java로 직접 구현하지 않고 플랫폼에 최적화된 C/C++ 코드로 OS 레벨에서 구현해 둔 것을 JNI(Java Native Interface)를 통해 호출하는 구조입니다.

이제 문제를 살펴보면

 

값이 2일때는 0번의 연산

연산을 한번만 하는 것은 4(루트 4)이므로 3은 4로 이동 후 연산을 진행하면 2번의 연산이 진행됩니다.(n+1, 루트 N)

다음 제곱수를 생각했을 때 9는 루트 처리 후 3의 값에 +1하면 됩니다.

 

즉 일반화를 진행하면

1. 현재 수가 완전제곱수라면: √N 연산 (연산 1회)
2. 그 외의 경우: +1 연산을 반복해서 완전제곱수로 만든 뒤, √ 연산

• 완전제곱수가 아니면, +1 연산을 통해 다음 완전제곱수로 이동한 뒤 √ 연산을 합니다.
• 이 과정을 반복하면서 N이 2가 될 때까지 연산 횟수를 누적합니다.
• 즉, N → 다음 제곱수 → √ → 반복, 이 과정을 통해 DP 없이도 최적의 연산 횟수를 구할 수 있습니다.

소스코드

public class Q6782 {
    private static int tc;
    private static Long N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= tc; t++) {
            N = Long.parseLong(br.readLine());
            sb.append("#").append(t).append(" ").append(solve(N)).append("\n");
        }
        System.out.println(sb);
    }

    private static long solve(long n) {
        long count = 0;

        while (n != 2) {
            long sqrt = (long) Math.sqrt(n);
            if (sqrt * sqrt == n) {
                n = sqrt;
                count++; // 한 번의 연산
            } else {
                long nextSquare = (sqrt + 1) * (sqrt + 1);
                count += nextSquare - n;
                n = nextSquare;
            }
        }

        return count;
    }
}

코드 설명

• solve(long n)
  n의 2로 만드는 최소 연산 값을 구하는 함수
  • n이 2가 아닐동안
    • Math.sqrt(n)을 통해 sqrt 값을 구해줍니다.(여기서 기본 스펙이 double이기 때문에 long으로 타입 캐스팅을 진행해줍니다.)
    • n이 제곱수인지를 판단해주기 위해 sqrt * sqrt = n인지 파악합니다
      • 제곱수라면
        • n = sqrt로 치환 후 count를 1 증가합니다.
      • 제곱수가 아니라면
        • 다음 제곱수까지 count를 증가시키고
        • n을 다음 제곱수로 치환합니다.