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

1. 문제 접근 방법 및 아이디어

이 문제의 핵심은 숫자 N을 2로 만드는 가장 빠른 방법을 찾는 것입니다.

1. 그리디
   • N이 완전제곱수라면 무조건 루트를 씌우는 것이 이득입니다.
   • 숫자가 비약적으로 작아지기 때문입니다.
2. 점프
   • N이 완전제곱수가 아니라면 N + 1을 반복해야 합니다.
   • 이때 1씩 더하며 체크하는 것이 아니라, N보다 큰 가장 가까운 완전제곱수까지 한 번에 더해버리는 것이 핵심 아이디어입니다.

2. 필요 개념 및 알고리즘

1. 그리디 알고리즘
   • 매 순간 N을 가장 작게 만들 수 있는 방법은 루트 씌우기 입니다.
   • N이 최대 범위가 10^12입니다. 1씩 더해서는 절대 시간 내에 풀 수 없기 때문입니다.

3. 어려웠던 점

1. 자료형과 시간초과
   • N이 최대 10^12이므로 반드시 long을 사용해야 합니다.
     • int를 쓰면 오버플로우로 인해 무한 루프나 잘못된 값이 나옵니다.
   • N이 완전제곱수가 아닐 때 N++을 반복하면 반드시 시간 초과가 발생합니다.
     • 다음 제곱수까지의 차이를 한 번에 더한다는 발상이 가장 어렵습니다.

4. 코드 풀이

4.1 N을 2로 만들기 위한 계산

// N이 2가 되면 종료
while (N != 2) {

// N에 루트를 계산
long root = (long) Math.sqrt(N);

// 루트 N이 정수인지 체크
// 정수이면 N을 갱신
if (root * root == N) {
	N = root;
	result++;
// 정수가 아니면 N+1 계산  
} else {
    long nextroot = root + 1;
	long nextN = nextroot*nextroot;
	result += (nextN - N) + 1 ;
	N = nextroot;

    }
}

• 루트 N이 정수인지 판별하는 방법은 루트 N * 루트 N의 값이 N과 같으면 완전제곱수입니다.
• (nextN-N)+1은 N보다 큰 가장 가까운 완전제곱수까지 가는 횟수에 루트 nextN을 계산한 횟수를 추가로 계산합니다.

4.2 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution_D5_6782_현주가좋아하는제곱근놀이 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine().trim());

		// tc 수행
		for (int tc = 1; tc <= T; tc++) {

			// 하나의 정수 N 입력, 횟수의 최솟값 초기화
			long N = Long.parseLong(br.readLine().trim());
			long result = 0;

			// 처리
			// N이 2가 되면 종료
			while (N != 2) {

				// N에 루트를 계산
				long root = (long) Math.sqrt(N);

				// 루트 N이 정수인지 체크
				// 정수이면 N을 갱신
				if (root * root == N) {
					N = root;
					result++;
                // 정수가 아니면 N+1 계산  
				} else {
					long nextroot = root + 1;
					long nextN = nextroot*nextroot;
					result += (nextN - N) + 1 ;
					N = nextroot;

				}
			}

			// 출력 내용 추가
			sb.append("#" + tc + " " + result + "\n");

		} // tc 종료

		// 출력
		System.out.println(sb);

	}

}