문제

x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.
※ 각 원 위의 점도 포함하여 셉니다.

예시

그림과 같이 정수 쌍으로 이루어진 점은 총 20개 입니다.

제한 사항

1 ≤ r1 < r2 ≤ 1,000,000

풀이

아이디어

• 일단 최대 반지름이 1,000,000이다? 무조건 O(N) 안으로 들어와야 하는 문제이겠구나.
  • 그러면 이중 for문으로 x, y를 돌면서 각각의 제곱의 합이 작은 원 반지름 제곱보단 크고 큰 원 반지름 제곱보다는 작은 것을 체크하는 식으로는 풀면 안 되겠구나.
  • 그렇다면, 변수를 x, y로 둘 게 아니라 둘 중 하나로 줄여야겠다. → 둘 중 하나를 나머지 하나로 표현할 방법을 찾아야겠다.

• 위의 수식처럼 원의 방정식을 요리조리 개조해서 y를 x에 대한 식으로 만들 수 있고, 이를 이용해서 아이디어를 낼 수 있다.
• 아이디어는 x를 1부터 r2까지 돌면서 현재 x값에 대해서 가질 수 있는 y의 최댓값과 최솟값을 얻어내서 그 사이의 점의 개수를 구하는 방식이다.
  • 이 때 y의 최댓값은 반지름이 r2일 때 위의 식에서 y 값에 내림(Math.floor)을 해 준 값이고, 최솟값은 반지름이 r1일 때 위의 식에서 y 값에 올림(Math.ceil)을 해 준 값이다. 그러면 현재 x 값에 대해서 가질 수 있는 y 값의 범위가 나오게 되고, 개수를 구할 수 있다.
  • 만약 x가 r1보다 커지게 된다면 y의 최솟값은 0으로 고정이 된다.
• 제 1사분면만 계산한 후 4배를 하면 답이 얻어진다.
  

이를 코드로 옮겨보면 다음과 같다.

코드

Javascript 코드

function solution(r1, r2) {
    var answer = 0;
    
    for(let x=1; x <= r2; x++) {
        let maxY = Math.floor(Math.sqrt(r2*r2 - x*x));
        let minY =  x >= r1 ? 0 : Math.ceil(Math.sqrt(r1*r1 - x*x));
        answer += maxY - minY + 1;
    }
    
    return answer * 4;
}

Python 코드

import math

def solution(r1, r2):
    answer = 0
    for x in range(r2+1):
        maxY = int(math.sqrt(r2**2 - x**2))
        minY = 0 if x >= r1 else math.ceil(math.sqrt(r1**2 - x**2))
        answer += (maxY - minY + 1)
        
    return answer * 4 - (r2 - r1 + 1) * 4