[프로그래머스] 두 원 사이의 정수 쌍 - Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/181187

프로그래머스

 

---

문제 개요

중심이 원점인 두 개의 원이 주어진다. 두 원은 서로 다른 크기의 반지름 r1과 r2를 가지고 있다. 이때, 두 원 사이에 있는 공간(즉, 작은 원과 큰 원 사이의 영역)에 x좌표와 y좌표가 모두 정수인 점의 개수를 구하는 문제

아이디어

1. 원의 방정식: 중심이 (0, 0)이고 반지름이 r인 원의 방정식(x2+y2=r2x^2 + y^2 = r^2x2+y2=r2)을 기반으로, 주어진 x에 대해 y의 가능한 값을 계산할 수 있다
2. 범위 설정: 두 원 사이의 공간에 있는 점을 찾으려면, 각 x값에 대해:
   • 큰 원 (r2)의 방정식에서 y의 최대 값을 찾고,
   • 작은 원 (r1)의 방정식에서 y의 최소 값을 찾습니다.
   • 큰 원에서 가능한 y의 최대 값은 y= √r2² - x ² ​
   • 작은 원에서 가능한 y의 최소 값은 y= √ r1² - x ² }
3. 계산 범위: x축 위에서 반지름이 주어졌을 때, 첫 번째 사분면에서 각 x값에 대해 가능한 정수 y값의 범위를 구하고, 이를 네 사분면에 대칭적으로 적용하여 전체 좌표를 구합니다.

 

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;

        for (int x = 1; x <= r2; x++) {
            long maxY_r2 = (long) Math.floor(Math.sqrt((long)r2 * r2 - (long)x * x));
            long minY_r1 = (long) Math.ceil(Math.sqrt((long)r1 * r1 - (long)x * x));
            
            answer += maxY_r2 - minY_r1 + 1;
        }
        
        return answer * 4;
    }
}