SWEA 6782 - 현주가 좋아하는 제곱근 놀이(dp를 통한 풀이)

문제 링크

문제 요약

n을 입력받는다. 해당 n은 다음과 같이 변화시킬 수 있다.
1. √n이 정수일 때 : n → √n
2. n → n + 1
해당 연산들은 각각 1의 시간이 소요되며, n을 2로 변화시키기까지 걸리는 시간을 구하라.

접근

• 입력이 10^12까지 가능하니 일반적인 완전탐색으로는 안 될 것
• 제곱수를 찾기 위해 모두 저장한 후, dp를 통해 수행시간 줄이기

풀이

1. 인덱스를 i라 한다면, arr[i][0]에는 i의 제곱수를 저장하고, arr[i][1]에는 해당 i^2에서 2까지 갈 때의 횟수를 저장하는 배열을 생성
2. 테스트 케이스의 값 n을 입력받음
3. n과 같거나 n보다 큰, 가장 가까운 제곱수를 findN 함수를 통해 탐색
4. 만약 해당 제곱수의 dp값이 저장되어 있다면 해당 값을 통해 출력
5. 만약 저장되어있지 않다면, 다시 재귀함수로 들어가 제곱수의 루트값에 대한 탐색을 시작함
   
   

코드

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

public class SWEA6783_dp {

	// 인덱스 : 루트n, arr[][0] : 제곱값, arr[][1] : 해당 제곱값에서 2를 만들기까지 필요한 횟수(DP)
	static long[][] arr = new long[1000002][2];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine()) + 1;
		long n;
		StringBuilder sb = new StringBuilder();

		// arr에 제곱수를 채워넣음
		for (long i = 2; i < 1000002; i++) {
			arr[(int) i][0] = i * i;
		}

		for (int tc = 1; tc < testCase; tc++) {
			n = Long.parseLong(br.readLine());
			sb.append("#").append(tc).append(" ");
			
			//2를 입력받았을 경우, 바로 return
			if (n == 2) {
				sb.append(0).append('\n');
				continue;
			}
			
			// count 함수를 통해 횟수 찾기
			long ans = count(n);

			sb.append(ans).append('\n');
		}
		System.out.println(sb);
	}

	// n을 입력받았을 때, n보다 크거나 작은 제곱수의 루트값을 반환하는 함수
	private static int findN(long n) {
		int left = 2;
		int right = 1000001;
		int mid = 0;
		long tmp;
		
		// 2를 return 해야 할 때만 예외처리
		if (n == 3 || n == 4)
			return 2;
		
		//이분탐색을 통해 찾는다.
		while (right - left > 1) {
			mid = (left + right) / 2;
			tmp = arr[mid][0];
			if (tmp == n || mid == 1000001) {
				return mid;
			}

			// 더 오른쪽에서 찾기
			if (tmp < n) {
				left = mid;
			} else {
				right = mid;
			}
			
			// 더 큰 수일 때 return
			if (tmp < n && arr[mid + 1][0] > n)
				return mid + 1;
			if (tmp > n && arr[mid - 1][0] < n) {
				return mid;
			}
		}
		return 0;
	}

	// n이 2가 될 때까지 필요한 횟수를 return
	static long count(long n) {
		// n == 2, 0 리턴
		if (n == 2) {
			return 0L;
		}

		// n보다 크거나 같은 제곱수의 루트값 반환
		int idx = findN(n);

		// 저장된 dp값이 없을 때
		if (arr[idx][1] == 0) {
			// 루트값에서 해당 값까지 걸리는 시간 탐색 후 출력
			arr[idx][1] = count(idx) + 1;
			return arr[idx][1] - n + arr[idx][0];
		}

		// 저장된 dp 값이 있을 때
		else {
			// 해당 제곱수에서 갈 수 있는 횟수 + 제곱수-현재수 (+1을 통해 이동해야 하는 수)
			return arr[idx][1] - n + arr[idx][0];
		}
	}
}

수학적으로 접근한 풀이

수학적으로 접근해 해당 수가 어떤 수의 제곱인지 판단 후, 옮겨가는 풀이
자바 내의 Math.sqrt() 함수를 제대로 사용하지 못해 해당 풀이를 떠올리지 못했던 것 같다.

코드

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

public class SWEA6782 {

	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine()) + 1;
		long n, tmp;
		int ans;
		StringBuilder sb = new StringBuilder();


		for (int tc = 1; tc < testCase; tc++) {
			n = Long.parseLong(br.readLine());
			sb.append("#").append(tc).append(" ");
			ans = 0;
			while(n != 2) {
				tmp = (long) Math.sqrt(n);
				// 제곱근이라면
				if(tmp * tmp == n) {
					// n에 루트를 씌워 변화시키기
					n = tmp;
					ans++;
				}else {
					// 현재 n이 tmp^2가 아니라면, n 다음의 제곱수는 (tmp+1)^2
					// (tmp+1)^2까지 필요한 횟수 더한 후, n 갱신
					ans += (tmp+1)*(tmp+1) - n;
					n = tmp + 1;
					ans++;
				}
			}
			sb.append(ans).append('\n');
		}
		System.out.println(sb);
	}
}