[Algorithm] 두 원 사이의 정수쌍

📋 문제

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

제한 사항

1 ≤ r1 < r2 ≤ 1,000,000

 

입출력 예

2

3

20

 

✏️ 풀이

우선 모든 경우를 탐색한다면 당연히 시간초과가 날 것이라고 생각했다. 처음에는 원 안에 무조건 사각형으로 점이 찍힐 것이라고 생각해서 지름 - 2의 제곱을 생각했다. 하지만 어쩐일인지 모든 테스트케이스를 통과하지 못했다. 생각해보니 다음과 같은 경우가 있었기 때문이다.

 

파란색 원을 기준으로 빨간 박스대로 점이 차있을 것이라고 생각했었다. 하지만 반지름에 따라 경우를 생각해줘야 하기 대문에 복잡해 질 수 있어 다른 방법을 생각하게 되었고 사분면 중에 한 부분만 계산해서 4를 곱해주는 방법을 생각해봤다.

 

처음에는 이중 for문을 이용해서 돌려보았으나 시간초과가 발생했다. 다시 시도한 방법은 가능한 정수쌍의 최소, 최대를 구하는 방법이었다.

피타고라스 정의를 이용해서 구하는 방법이다. 위의 예시는 y가 2일 때의 예시이다. 바깥쪽에 위치하는 원의 y가 2일때를 구한다면 (반지름^2 - y^2)의 제곱근을 구해주면 된다. 내부 원도 마찬가지로 계산하고 외부 원은 내림, 내부 원은 올림하여 사이에 위치할 수 있는 정수쌍의 수를 구하고 answer에 더해준다. 이렇게 되면 사분면 중 한 부분에서 한쪽 축을 제외한 부분의 가능한 정수쌍을 구할 수 있다. 따라서 마지막에 4배를 해주고 반환하면서 문제를 해결했다.

 

⌨️ 코드

function solution(r1, r2) {
  var answer = 0;

  for (let i = 1; i <= r2; i++) {
    const min = Math.ceil(Math.sqrt(r1 ** 2 - i ** 2)) || 0;
    const max = Math.floor(Math.sqrt(r2 ** 2 - i ** 2));

    answer += max - min + 1;
  }

  return answer * 4;
}