[SW Expert] 6782. 현주가 좋아하는 제곱근 놀이

생각

Github - https://github.com/hellojdh/Code/blob/master/src/swexpert/d5/Q6782.java

2이상의 정수 N이 주어진다. N은 다음 2개의 규칙으로 바꿀 수 있다.
1) sqrt(N)이 정수라면 N을 sqrt(N)으로 바꿀 수 있다. 
2) 그렇지 않다면 N을 N+1로 바꿀 수 있다.

처음 생각

처음엔 생각나는데로 풀이를 시작했다. 규칙대로 루트 N 값이 정수라면 N을 루트 N으로 바꿔주고, 그렇지 않다면 1씩 증가시켜주었다.

▶ N이 최대 10^12으로 숫자가 상당히 커서 시간 초과가 났다.

▶ 루트 N이 정수인지 확인한 방법은 간단하게 다음과 같이 확인하였다.

1 2	double t = Math.sqrt(n); if((int)t == t) {}

▶ Java에서 제공해주는 Math class의 sqrt 메소드를 사용해서 루트 n을 구한뒤, 이값을 정수형으로 type casting 해주어 둘이 같다면 원래부터 정수인 것으로 판단하였다.

다음 생각

시간 초과가 나는 부분은 1씩 증가하는 부분이라는 생각이 들어 해당 부분을 줄일 방법을 생각해 보았다.

▶ 첫 번째 생각은 테스트 케이스가 총 10000개이므로 배열에 모든 가능성을 미리 구해두고 꺼내는 방법이였다.

▶ 두 번째 생각은 결국 루트를 취했을 때, 정수가 될때까지 1씩 증가시키는 것이였으므로 현 루트를 취한 값에서 올림을 하여 다음 번 정수가 만들어지는 루트값을 찾는 방법이였다. 구현은 요 방법으로 하였다.

다다음 생각

작은 숫자로 생각을 해보자. 예를들어 11 이라는 숫자가 있다. sqrt(11) = 3.xxx 이 나올 것이다. 이 상태에서 올림을 해주면 정수 4가 되고, 이를 제곱해주면 16이 나오게된다. 따라서 11이 루트를 취하고 싶으면 16까지 1씩 증가해야한다.

▶ 여기서 (int)sqrt(11)+1을 통해서 4를 찾았고 11이 루트를 취하기 위해서는 16이 되어야한다는 사실을 이미 알고 있으므로 16-11을 통해서 5번의 과정을 거쳐야 하는 것을 단 번에 알 수 있다. 수가 커질 수록 제곱의 차이도 커지므로 1씩 더하는 과정을 크게 생략할 수 있다.

다다다음 생각

N의 범위가 10^12 이므로 long 타입으로 선언을 해준 뒤, 루트 N이 정수라면 바로 N을 루트 N으로 바꿔주고 그렇지 않다면 위의 과정을 통해서 (int)sqrt(N)+1의 제곱에서 N을 빼준 뒤 N을 (int)sqrt(N)+1로 바꿔주었다.

다다다다음 생각

이렇게 해서도 시간 초과가 나면 모두 미리 구해놓고 답만 쏙쏙 출력할 생각이였으나 숫자가 커도 sqrt(N)으로 수가 작아지기 때문에 시간이 조금 밖에 안걸렸다.

▶ 루트씩 크기가 작아지기 때문에 시간 복잡도는 O(logN) 일 것이다.

방안

1) Java 풀이

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

package swexpert.d5;   import java.io.*;   public class Q6782 {     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));           int tc = Integer.parseInt(br.readLine());         for(int z=1;z<=tc;z++) {             // 10^12             long n = Long.parseLong(br.readLine());             int result = 0;             while(n!=2) {                 double t = Math.sqrt(n);                 if((int)t == t) {                     n = (int)t;                 }else {                     t = (int)t;                     result += ((t+1)*(t+1)-n);                     n = (int)Math.sqrt((t+1)*(t+1));                 }                 result++;             }             bw.write("#"+z+" "+result+"\n");         }         bw.flush();     }// end of main }// end of class