---

📐 해당 문제를 보고 피타고라스의 정리가 떠올랐다.
$\sqrt{ x^2 + y^2} = C$(거리)
즉, $x^2 + y^2 = C^2$ 가 된다.

---

점을 찍을수 있는 모든 좌표는

(0, 0), (0, 2), (0, 4)
(2, 0), (2, 2), (2, 4)
(4, 0), (4, 2), (4, 4)

9가지가 있다.

• (0, 0) : $\sqrt{ 0^2 + 0^2}$ = 0, 0 $\leq$ 4 (가능)
• (0, 2) : $\sqrt{ 0^2 + 2^2}$ = 2, 2 $\leq$ 4 (가능)
• (0, 4) : $\sqrt{ 0^2 + 4^2}$ = 4, 4 $\leq$ 4 (가능)
• (2, 0) : $\sqrt{ 2^2 + 0^2}$ = 2, 2 $\leq$ 4 (가능)
• (2, 2) : $\sqrt{ 2^2 + 2^2}$ = $\sqrt{ 8}$ $\leq$ 4 (가능)
• (2, 4) : $\sqrt{ 2^2 + 4^2}$ = $\sqrt{ 20}$ $>$ 4 (불가능)
• (4, 0) : $\sqrt{ 4^2 + 0^2}$ = 4, 4 $\leq$ 4 (가능)
• (4, 2) : $\sqrt{ 4^2 + 2^2}$ = $\sqrt{ 20}$ $>$ 4 (불가능)
• (4, 4) : $\sqrt{ 4^2 + 4^2}$ = $\sqrt{ 32}$ $>$ 4 (불가능)

총 6가지가 가능하다.
굉장히 쉽게 생각하여 바로 코드를 작성하여 제출했다

---

💻 최종 코드 💻

class Solution {
    public long solution(int k, int d) {
        long cnt = 0;
        for (int x = 0; x <= d; x += k) {
            for (int y = 0; y <= d; y += k) {
                if (x * x + y * y <= d * d) {
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int k = 1;
        int d = 5;
        System.out.println(sol.solution(k, d));
    }
}

---

?!

그제서여 보이는 제한사항....

100만이 넘어가는 큰 수는 시간도 엄청나게 오래걸리고, 두개의 반복문을 사용해 모든 쌍을 탐색하기 때문에 시간이 $O((d/k)²)$ 만큼 소요된다.

---

📌개선 코드

• 반복문 안에서 계산되는것보다 미리 계산을 해놓는다.

long dSquare = (long) d * d;

• for문도 $x$ 값을 제대로 처리하기 위해 long타입 변환

for (long x = 0; x <= d; x += k)

• $x$ 값에 대해 가능한 $y$값의 최대값 계산.
• 계산값이 크기때문에 미리 $x$와 $y$의 최대값을 보장한다.

long y = (long) Math.sqrt(dSquare - x * x);

• $y$가 $k$의 배수로 증가하는 경우, 가능한 배수의 개수를 구함.
• + 1 은 $y$ 값이 0부터 시작하므로, 0도 포함하기 위해 추가함.

cnt += (y / k) + 1;

---

💻 최종 코드 💻

class Solution {
    public long solution(int k, int d) {
        long cnt = 0;
        long dSquare = (long) d * d;
        for (long x = 0; x <= d; x += k) {
            long y = (long) Math.sqrt(dSquare - x * x);
            cnt += (y / k) + 1;
        }
        return cnt;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int k = 1000000;
        int d = 1000000;
        System.out.println(sol.solution(k, d));
    }
}

👏👏👏👏👏👏👏👏👏