[코딩테스트] 23/12/04 - 두 원 사이의 정수 쌍 (Level2)

🌜 프로그래머스 링크

문제 설명

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

제한사항

• 1 ≤ r1 < r2 ≤ 1,000,000

문제풀이

• 원크기 전부를 계산했더니 시간초과가 발생했다.
• 원을 4등분하여 제1사분면의 점 개수를 구한후 4배 곱해준다.

1. i를 1 ~ r2 까지 순회하면서 x = i 와 두 원의 방정식과의 교점(s,e)을 구한다.
2. s는 정수 쌍 속하는 범위의 시작이 되고, e는 범위의 끝이 된다.
   • 반지름이 r2인 원과 x=i인 직선의 교점에서 내림(int 혹은 math.floor)을 적용하여 범위의 끝 값인 e를 구한다.
   • i 값이 r1보다 작으면, 반지름이 r1인 원과 x=i인 직선에서 x좌표가 0이 아닌 교점이 존재하므로 올림을 적용하여(math.ceil) 범위의 시작인 s값을 구한다.
   • i값이 r1보다 크거나 같다면 범위의 시작 s는 무조건 0이다.
3. s와 e 사이에 속하는 모든 정수의 개수를 구하고 answer 값에 더한다.
4. for문 순회 후 도출된 answer 값에 4를 곱하여 전체 사분면의 정수 쌍의 개수를 구한다.

Github 링크

코드 (C++)

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

  for (int i = 1; i <= r2; ++i)
  {
    int e = floor(sqrt(pow(r2,2) - pow(i,2)));        
    int s;
    if (i < r1)
      s = ceil(sqrt(pow(r1,2) - pow(i,2)));
    else
      s = 0;
    answer += e - s + 1;        
  }
  return answer * 4;
}