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

홍성진·2023년 4월 26일
0

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

원점을 중심으로 하는 원의 반지름 r1, r2가 주어질 때, 두 원 사이에 있는 격자점의 개수를 구하는 문제입니다. r2는 100만까지 커질 수 있기 때문에 단순히 정사각형을 순회하면 시간초과가 납니다. 원의 방정식 x^2 + y^2 = r^2을 이용해서 한 사분면만 계산하는 방식으로 풀었습니다. 오버플로우가 나지 않게 long으로 계산해야 합니다.

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        long l1 = r1;
        long l2 = r2;
        
        for (long i = 1; i <= l2; i++) {
            if (i > l1) {
                answer += (int) Math.sqrt(l2 * l2 - i * i) + 1;
                continue;
            }
            
            if (Math.sqrt(l1 * l1 - i * i) - (int) Math.sqrt(l1 * l1 - i * i) == 0) {
                answer++;
            }
            answer += (int) Math.sqrt(l2 * l2 - i * i) - (int) Math.sqrt(l1 * l1 - i * i);
        }
        
        return answer * 4;
    }
}

0개의 댓글