[자바] SWEA 6782 : 현주가 좋아하는 제곱근 놀이 (D5)

[자바] SWEA 6782 : 현주가 좋아하는 제곱근 놀이 (D5)

• SWEA 6782 : 현주가 좋아하는 제곱근 놀이

---

풀이

방향성 생각

• 수학 문제.
• 처음에는 그냥 무지성으로 BFS를 때려박았다.
• 10*12에서 루트 씌우다보면 금방 2로 갈거같았는데, 현재 x보다 크면서 가장 가까운 제곱근까지 가는 경우에 거리를 미리 알 수 있음에도 불구하고 BFS로 보내면 너무 오래걸린다.
• 현재 x보다 크면서 가장까운 제곱근까지 보내고 루트를 씌우면 t+1만큼 걸리면서 작아지는 방향으로 이동가능하다.

 

전체코드

import java.io.*;

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

        for (int tc = 1; tc <= TC; tc++) {
            long N = Long.parseLong(br.readLine());
            long x = N;
            long t = 0;

            while (true) {
                if (x == 2) break;

                double xSqrt = Math.sqrt(x);
                long xSqrtInt = (long) xSqrt;

                if (xSqrt == xSqrtInt) {
                    t += 1;
                    x = xSqrtInt;
                } else {
                    long xClose = (xSqrtInt + 1) * (xSqrtInt + 1);
                    t += xClose - x + 1;
                    x = (long) Math.sqrt(xClose);
                }
            }
            System.out.println("#" + tc + " " + t);
        }
    }
}

코멘트

*